eolymp
bolt
Try our new interface for solving problems
Problems

Сочинитель стихов

Сочинитель стихов

Time limit 2 seconds
Memory limit 64 MiB

Начинающий поэт Вася разработал конечный автомат для упрощения процесса сочинения стихов. Этот автомат имеет N состояний, при этом переход из состояния в состояние осуществляется по K возможным рифмам. Автомат имеет одно начальное состояние a и одно конечное состояние b. Результатом работы сочинителя стихов является некоторая последовательность рифм, принимаемая автоматом, на которую Вася накладывает готовые стихи.

Для того, чтобы стихи не были слишком однообразными, после каждого перехода Вася несколько изменяет автомат. А именно, как только происходит переход из состояния i в состояние j по рифме k, Вася стирает все переходы, исходящие из состояния i по рифме k, а также все переходы, ведущие в состояние j по рифме k.

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

Input data

Первая строка входного файла содержит четыре целых числа – количество состояний автомата N (1N50), количество рифм, которые использует Вася в своих стихах K (1K50), а также номера начального и конечного состояний a и b (1abN). Вторая строка содержит одно целое число – количество переходов в автомате М (1М1000). Далее следуют М строк, каждая из которых описывает один переход в формате u_i, v_i, k_i, означающий, что из состояния u_i можно перейти в состояние v_i по рифме k_i.

Output data

В первой строке выходного файла выведите максимальное количество стихов Z, которые Вася может сочинить с помощью своего автомата. Далее выведите Z строк, по одной для каждого стиха. Описание стиха выводите в формате

s_{1 }k_1 s_2 k_2 … s_l_{-1} k_l_{-1} s_l

где s_1 = a, s_l = b, k_i – рифмы, по которым производится переход, а S_i – состояния в порядке прохода.

Examples

Input example #1
9 5 1 9
12
1 2 1
1 3 1
1 4 1
4 5 1
3 5 1
2 5 1
5 6 1
5 7 1
5 8 1
8 9 1
7 9 1
6 9 1
Output example #1
1
1 1 4 1 5 1 8 1 9