Рабочее место участника

Полицейский гонится за преступником по музею. В начале погони каждый из них находится в одной из `n` комнат здания, некоторые комнаты соединены дверями.

Непосредственно перед началом погони в здании сработала сигнализация, и все двери закрылись. Музей использует сверхсовременную систему охраны — каждая дверь принадлежит одному из `k` контуров безопасности. Полицейский может с помощью специального пульта управления блокировать и разблокировать все двери некоторого контура. При этом с целью обеспечения безопасности операции он может одновременно разблокировать не более одного контура. Полицейский впервые попал на такое ответственное задание, поэтому очень волнуется. Чтобы случайно не провалить операцию, каждый раз, перейдя из одной комнаты в другую, он блокирует все двери. При этом он очень инициативен и каждую минуту переходит из комнаты в комнату.

Благодаря системе камер, установленной в музее, полицейский в любой момент знает, где находится преступник. Однако поскольку система видеонаблюдения находится в состоянии тестовой эксплуатации, данная информация доступна также во всех комнатах, поэтому преступник тоже знает, где находится полицейский. Преступник наблюдает за всеми перемещениями полицейского. Каждый раз, после того как полицейский переходит из одной комнаты в другую, перед тем, как полицейский заблокирует двери, преступник тоже может перебежать в одну из соседних комнат. Разумеется, он может пробегать только через двери контура, который в настоящее время разблокирован.

Преступник хочет добраться до выхода (который находится в комнате с номером 1), а полицейский — поймать преступника. Если полицейский врывается в комнату, где находится преступник, то преступник не успевает убежать в другую комнату, и полицейский арестовывает его. Если преступник оказывается в комнате с выходом, то он немедленно покидает здание и скрывается в близлежащих районах.

Полицейский хочет как можно быстрее поймать преступника или, если это невозможно, то как можно дольше задержать его внутри здания, чтобы дождаться помощи. Преступник же хочет либо как можно быстрее сбежать, либо как можно дольше бегать от полицейского (если первое невозможно).

Определите, сможет ли полицейский поймать преступника, и если да, то какое минимальное количество перемещений из комнаты в комнату ему для этого потребуется. Если полицейский не сможет поймать преступника, то определите, сможет ли тот убежать, и если да, то сколько переходов из комнаты в комнату ему для этого потребуется.

Первая строка входного файла содержит три числа: `n`, `m` и `k` — количество комнат, дверей и контуров соответственно (`4\ ≤\ n\ ≤\ 300`, `4\ ≤\ m\ ≤\ 10\ 000`, `1\ ≤\ k\ ≤\ 10`). Следующие `m` строк содержат по три целых числа — для каждой двери указаны номера комнат, которые она соединяет, и номер контура безопасности, к которому она принадлежит.

Последняя строка входного файла содержит два различных целых числа — номера комнат, в которых в начале погони находятся полицейский и преступник, соответственно.

На первой строке выходного файла выведите "Caught", если полицейскому удастся поймать преступника, "Escaped", если преступнику удастся убежать, и "Endless", если ни один из этих случаев не имеет место.

Если полицейскому удастся поймать преступника, или преступнику удастся сбежать, то на второй строке выходного файла выведите число переходов полицейского из комнаты в комнату при оптимальных действиях обеих сторон.

5 4 2
1 2 2
2 3 1
3 5 2
5 4 1
4 3

Endless

4 3 2
1 2 2
2 3 1
4 3 2
4 2

Escaped
1

5 4 2
1 2 2
3 2 1
4 3 1
5 4 1
5 2

Caught
3