eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Побег

Побег

Лимит времени 3 секунды
Лимит использования памяти 256 MiB

Вы со всей силой ударили императора Лича и убили его. К выходу вела лестница. Вы взобрались наверх. Выпили воды из бассейна. Почувствовали себя лучше. Кармическая ящерица проникает сквозь Ваши доспехи и убивает Вас. Вы умираете...

После эпической схватки с императором Лича, герою надо выбраться из подземелья, состоящего из n комнат и n - 1 коридора, соединяющего их. Он стартует из комнаты 1 и должен достичь комнату t, двигаясь только по коридорам. Все комнаты достижимы из 1. Будучи контуженным прошлой ночью, герой начинает движение с 0 очками (HP). Они показывают уровень его здоровья – если он падает ниже нуля, то история героя трагически заканчивается.

В некоторых комнатах находятся монстры – с монстром следует сражаться, поэтому герой всегда в этом случае потеряет очки (HP). В некоторых других комнатах расположены магические бассейны – каждый бассейн восстанавливает некоторое количество очков жизни. Верхнего лимита жизни героя не существует. Каждую комнату можно посетить несколько раз, но получение или потеря HP случается только раз, в момент первого визита.

Определите, сможет ли герой выбраться из подземелья живым.

Входные данные

Первая строка содержит количество тестов tests. Структура каждого теста следующая:

Первая строка содержит два числа: количество комнат n (2 n 200000) и количество комнат, являющимися выходом t (2 t n). Вторая строка содержит n целых чисел в промежутке от -10^6 до 10^6, i-ое из которых указывает на количество очков (HP), получаемое в i-ой комнате (отрицательное число означает монстра, положительное - бассейн, ноль означает что комната пуста). Первая комната не содержит монстра, но бассейн может находиться в ней. Комната, являющаяся выходом, может содержать как монстра, так и бассейн, и монстра следует обязательно убить перед выходом.

Следующие n - 1 строк задают описания коридоров. Каждая из них содержит пару целых чисел - концы коридора.

Выходные данные

Для каждого теста вывести в отдельной строке слово escaped если побег возможен или trapped иначе.

Пример

Входные данные #1
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
Выходные данные #1
escaped
trapped
Источник 2013 ACM ICPC Central Europe Regional Contest, Краков, Ноябрь 15-17, Задача E