Escape

You hit the emperor lich with full force and slay it. There is a stair leading upwards here. You climb upstairs. You drink from the pool. You feel much better. The karmic lizard punches through your armor and hits you. You die...

After an epic fight with the emperor lich, the hero has to get out of a dungeon of $n$ chambers joined by $n - 1$ corridors. He starts in chamber $1$ and must reach chamber $t$, moving only along corridors. Every chamber is reachable from chamber $1$. Bruised from the last fight, the hero begins the journey with $0$ hit points (HP). HP is his health: the moment it falls below zero, his story ends there as a tragic one.

Some chambers hold monsters. A monster must be fought, and the fight always takes some of the hero's HP. Other chambers hold magic pools, and every pool restores some HP. The hero's health has no upper limit. He can walk through a chamber as many times as he likes, but its gain or loss of HP happens only once, on the very first visit.

Determine whether the hero can escape the dungeon alive.

The first line contains the number of test cases $T$. The descriptions of the test cases follow.

The first line of each test case contains two integers: the number of chambers $n$ ($2 \le n \le 200\,000$) and the number of the exit chamber $t$ ($2 \le t \le n$). The second line contains $n$ space separated integers between $-10^6$ and $10^6$. The $i$-th of them is the HP change in chamber $i$: negative denotes a monster, positive denotes a pool, and zero means the chamber is empty. Chamber $1$ does not hold a monster, but a pool is possible there. The exit chamber may hold a pool or a monster, and that monster has to be fought before escaping.

The next $n - 1$ lines describe the corridors, one per line. Each line holds a pair of integers, the two chambers that the corridor connects.

For each test case print a single line containing the word escaped if escape is possible, or trapped otherwise.