eolymp
bolt
Try our new interface for solving problems
Məsələlər

Замки и ключи

Замки и ключи

Zaman məhdudiyyəti 10 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Волшебник находится в лабиринте из V комнат и V - 1 дверей. Каждая дверь соединяет пару комнат в обоих направлениях. известно, что между любыми двумя комнатами всегда существует путь, проходящий через некоторую последовательность дверей. Также имеются C замков и C ключей C разных цветов(каждый ключ имеет свой цвет) от дверей, соединяющих комнаты в лабиринте; каждая дверь имеет не более одного замка, и в каждой комнате находится не более одного ключа. Вошебнику не стоит труда пройти через систему замков, но проблема состоит в том, что он забыл свою волшебную книгу, без которой его волшебство не действует. На данный момент волшебник находится в комнате X, и он хочет добраться до своей волшебной книги, которая находится в комнате Y, за кратчайшее время. На каждом шаге волшебник может пройти в соседнюю комнату через дверь. Конечно, если дверь на замке, то у него должен быть ключ того же цвета что и замок (если вдруг до этого эта дверь уже не была открыта). Волшебник может нести с собой только один ключ. После того как волшебник подберет ключ, он не может его оставить где-нибудь в лабиринте чтобы потом его снова взять. Как только дверь становится открытой, ключ выбрасывается, так как он больше становится не нужным.

По заданному лабиринту и положениям C ключей и C замков, определите как добраться до Y из X, если это возможно. Любой путь, длина которого не больше 4^{ . }(C + 1)^{ . }V, является допустимым.

Giriş verilənləri

Первая строка каждого теста содержит четыре целых числа: количество комнат V (1V1500) в лабиринте, количество замков C (0C < V), и номера комнат X и Y. Комнаты пронумерованы числами 0, 1,..., V - 1. Далее идет (возможно пустая) строка из C целых чисел, описывающих местоположение каждого ключа, в порядке возрастания цветов. Следующие V - 1 строк описывают лабиринт: каждая строка содержит три целых числа A B L, обозначающих тот факт, что между комнатами A и B имеется дверь, которая открывается ключем цвета L, если 0L < C; значение -1 для L означает что дверь не содержит замка.

Последняя строка содержит V, C, X, Y = 0, 0, 0, 0 и не обрабатывается.

Çıxış verilənləri

Выходные данные для каждого теста следует выводить в отдельной строке. Если решения не существует, вывести "Impossible". Иначе следует вывести весь путь в формате L: V_0,...,V_L, где L4(C + 1)V длина пути от X до Y, а X = V_0, V_1,..., V_L_{-1}, V_L = Y последовательность из L + 1 вершин, посещаемых в указанном порядке. Перед каждой вершиной в выводимом пути следует печатать один пробел.

Nümunə

Giriş verilənləri #1
1 0 0 0


3 1 0 2
1
0 1 -1
0 2 0

3 2 0 2
1 2
0 1 1
0 2 0

5 3 0 4
2 0 3
0 1 0
0 2 -1
1 3 1
2 4 2

0 0 0 0
Çıxış verilənləri #1
0: 0
3: 0 1 0 2
Impossible
10: 0 2 0 1 0 1 3 1 0 2 4