eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Сочинитель віршів

Сочинитель віршів

Ліміт часу 2 секунди
Ліміт використання пам'яті 64 MiB

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

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

Потрібно визначити максимальний набір віршів, які Вася може створити, використовуючи свій автомат таким чином. Після того, як якийсь перехід витерто, він уже більше ніколи в історії життя цього автомата не буде відновленим, так як Вася не бажає повторюватись.

Вхідні дані

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

Вихідні дані

У першому рядку вихідного файлу виведіть максимальну кількість віршів 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 – стан у порядку проходження.

Приклад

Вхідні дані #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
Вихідні дані #1
1
1 1 4 1 5 1 8 1 9