Description

在与巫妖王进行了一场史诗般的战斗后，英雄们试图从地牢中逃脱。这个地牢由 $n$ 个房间和 $n-1$ 条走廊组成，形成一个树状结构。英雄最初位于 $1$ 号房间，他必须到达 $t$ 号房间才能成功逃离地牢。

英雄的初始精力值为 $0$。如果英雄的精力值在任何时候低于 $0$，他将立即死亡，游戏结束。每个房间都有特殊的效果：有些房间有怪兽，会减少英雄的精力；有些房间有魔泉，可以恢复英雄的精力；还有些房间空无一物。所有房间的效果只在英雄第一次进入时触发，之后再次进入不会产生任何效果。

英雄的精力值没有上限，他可以多次经过同一个房间。注意，$1$ 号房间不会有怪兽，但可能有魔泉；$t$ 号房间可能有怪兽或魔泉，如果有怪兽，英雄必须击败它才能逃离。

Format

Input

第一行包含一个整数 $T$，表示测试数据组数。

对于每组测试数据：

• 第一行包含两个整数 $n$ 和 $t$，分别表示房间数量和目标房间编号。
• 第二行包含 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个房间的效果（负数表示怪兽，正数表示魔泉，$0$ 表示空）。
• 接下来 $n-1$ 行，每行两个整数 $a$ 和 $b$，表示房间 $a$ 和 $b$ 之间有一条走廊。

Output

对于每组测试数据，输出一行：如果英雄能够逃脱，输出 escaped；否则输出 trapped。

Samples

2
7 7
0 -3 2 2 3 -4 0
1 2
2 3
2 4
1 5
5 6
6 7
3 2
3 3 -4
1 3
2 3

escaped
trapped

Limitation

$1\mathrm{s},512\mathrm{MB}$

Subtask

对于 $100\%$ 的数据，$1\leqslant T\leqslant 10$，$2\leqslant n\leqslant 200\ 000$，$2\leqslant t\leqslant n$，每个房间效果的绝对值不超过 $10^6$。