|
Цветной лабиринт
(Время: 1 сек. Память: 16 Мб Сложность: 38%)
В одном из парков одного большого города недавно был организован новый аттракцион Цветной лабиринт. Он состоит из n комнат, соединенных m двунаправленными коридорами. Каждый из коридоров покрашен в один из ста цветов, при этом от каждой комнаты отходит не более одного коридора каждого цвета. При этом две комнаты могут быть соединены любым количеством коридоров.
Человек, купивший билет на аттракцион, оказывается в комнате номер один. Кроме билета, он также получает описание пути, по которому он может выбраться из лабиринта. Это описание представляет собой последовательность цветов c1…ck. Пользоваться ей надо так: находясь в комнате, надо посмотреть на очередной цвет в этой последовательности, выбрать коридор такого цвета и пойти по нему. При этом если из комнаты нельзя пойти по коридору соответствующего цвета, то человеку приходится дальше самому выбирать, куда идти.
В последнее время в администрацию парка стали часто поступать жалобы от заблудившихся в лабиринте людей. В связи с этим, возникла необходимость написания программы, проверяющей корректность описания и пути, и, в случае ее корректности, сообщающей номер комнаты, в которую ведет путь.
Описание пути некорректно, если на пути, который оно описывает, возникает ситуация, когда из комнаты нельзя пойти по коридору соответствующего цвета.
Входные данные
Первая строка входного файла INPUT.TXT содержит два целых числа n (1 ≤ n ≤ 10000) и m (1 ≤ m ≤ 100000) - соответственно количество комнат и коридоров в лабиринте. Следующие m строк содержат описания коридоров. Каждое описание содержит три числа u (1 ≤ u ≤ n), v (1 ≤ v ≤ n), c (1 ≤ c ≤ 100) - соответственно номера комнат, соединенных этим коридором, и цвет коридора. Следующая, (m+2)-ая строка входного файла содержит длину описания пути - целое число k (0 ≤ k ≤ 100000). Последняя строка входного файла содержит k целых чисел, разделенных пробелами, - описание пути по лабиринту.
Выходные данные
В выходной файл OUTPUT.TXT выведите строку INCORRECT, если описание пути некорректно, иначе выведите номер комнаты, в которую ведет описанный путь. Помните, что путь начинается в комнате номер один.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3 2
1 2 10
1 3 5
5
10 10 10 10 5 | 3 |
| 2 | 3 2
1 2 10
2 3 5
5
5 10 10 10 10 | INCORRECT |
| 3 | 3 2
1 2 10
1 3 5
4
10 10 10 5 | INCORRECT |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
