Сочинитель віршів
Поет початківець Вася розробив кінцевий автомат для спрощення процесу придумування віршів. Цей автомат має N станів, при цьому перехід із стану у стан здійснюється по K можливим рифмам. Автомат має один початковий стан a і один кінцевий стан b. Результатом работи сочинителя віршів є деяка послідовність рим, що приймається автоматом, на яку Вася накладаєт готові вірші.
Для того, щоб вірші не були занадто однотипними, після кожного переходу Вася дещо змінює автомат. А саме, як тільки відбувається перехід зі стану i у стан j по римі k, Вася витирає усі переходи, що виходять зі стану i по римі k, а також усі переходи, які ведуть у стан j по римі k.
Потрібно визначити максимальний набір віршів, які Вася може створити, використовуючи свій автомат таким чином. Після того, як якийсь перехід витерто, він уже більше ніколи в історії життя цього автомата не буде відновленим, так як Вася не бажає повторюватись.
Вхідні дані
Перший рядок вхідного файлу містить чотири цілих числа – кількість станів автомата N (1 ≤ N ≤ 50), кількість рим, які використовує Вася у своїх віршах K (1 ≤ K ≤ 50), а також номери початкового і кінцевого станів a та b (1 ≤ a ≠ b ≤ N). Другий рядок містить одне ціле число – кількість переходів у автоматі М (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 – стан у порядку проходження.