Обходчик лабиринтов
(Время: 2 сек. Память: 16 Мб Сложность: 65%)
В скором времени на телеэкраны одной страны выйдет новое шоу «Двое в лабиринте». Его сюжет будет состоять в том, что два участника будут помещены в лабиринт. Их целью является поиск выхода из данного лабиринта. Первый, кто найдет выход, получит крупный денежный приз.
Однако, прежде чем шоу выйдет на экраны, лабиринты должны быть сертифицированы Государственным Бюро по Сертификации Лабиринтов. В своей работе бюро использует специальные машины, называемые обходчиками лабиринтов.
Поскольку в силу специфики работы этих машин для каждого лабиринта приходится строить нового обходчика, Вам поручено провести компьютерное моделирование обхода лабиринта обходчиком.
Лабиринт состоит из n комнат, соединенных m коридорами. На концах коридора имеются две двери, одна из которых открывается только из коридора, в вторая только из комнаты, из которой коридор выходит, таким образом, движение по коридору разрешено только в одну сторону. Кроме этого, каждый из коридоров покрашен в один из k цветов (это сделано для того, чтобы немного облегчить участникам нахождение выхода из лабиринта). Цвет коридора указан на соответствующей ему двери в комнате, из которой он выходит. При этом из комнаты могут выходить несколько коридоров одного цвета.
Обходчик лабиринтов работает по программе, которая состоит из L инструкций. Каждая инструкция – это номер цвета (число от 1 до k). Обход лабиринта начинается в комнате номер s и совершается следующим образом: обходчик поочередно считывает инструкции и на каждом шаге выбирает один из коридоров, покрашенных в цвет, указанный в этой инструкции. Если такого коридора не находится, то обходчик «зависает».
Так как на каждом шаге у обходчика может быть не один вариант выбора коридора, то комната, в которой он окажется после выполнения программы может определяться неоднозначно.
Ваша задача состоит в том, чтобы по описанию лабиринта и программе для обходчика определить, в каких комнатах обходчик может оказаться после выполнения соответствующей программы.
Входные данные
Первая строка входного файла INPUT.TXT содержит три целых числа: n, m, k (1 ≤ n, k ≤ 1000, 0 ≤ m ≤ 10000). Далее идут m строк, описывающих коридоры. Описание каждого коридора состоит из трех целых чисел: u, v, c (1 ≤ u, v ≤ n, 1 ≤ c ≤ k). Их значения таковы: u - номер комнаты, из которой выходит коридор, v - номер комнаты, в которую ведет коридор, c цвет этого коридора. Коридор может вести из комнаты в саму себя, между двумя комнатами может существовать несколько коридоров (более того, несколько коридоров одного цвета).
(m+2)-ая строка входного файла содержит целое число L (1 ≤ L ≤ 1000). (m+3)-ая строка содержит L целых чисел от 1 до k – программы для обходчика лабиринта.
Последняя строка входного файла содержит целое число s (1 ≤ s ≤ n).
Выходные данные
В выходной файл OUTPUT.TXT следует вывести слово Hangs в случае, если обходчик «зависает» независимо от того, какие коридоры он выбирает при существовании нескольких коридоров одного цвета.
Иначе, выведите на первой строке выходного файла слово OK, во второй – количество r комнат, в которых обходчик может оказаться после выполнения программы. В третьей строке выходного файла в этом случае выведите номера этих комнат в возрастающем порядке.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4 6 2
1 2 1
1 2 2
1 3 1
1 3 2
3 4 2
3 3 2
2
1 2
1 | OK
2
3 4 |
| 2 | 4 6 2
1 2 1
1 2 2
1 3 1
1 3 2
3 4 1
3 3 1
2
1 2
1 | Hangs |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
