Начинающий поэт Вася разработал конечный автомат для упрощения процесса сочинения стихов. Этот автомат имеет \textbf{N} состояний, при этом переход из состояния в состояние осуществляется по \textbf{K} возможным рифмам. Автомат имеет одно начальное состояние \textbf{a} и одно конечное состояние \textbf{b}. Результатом работы сочинителя стихов является некоторая последовательность рифм, принимаемая автоматом, на которую Вася накладывает готовые стихи. Для того, чтобы стихи не были слишком однообразными, после каждого перехода Вася несколько изменяет автомат. А именно, как только происходит переход из состояния \textbf{i} в состояние \textbf{j} по рифме \textbf{k}, Вася стирает все переходы, исходящие из состояния \textbf{i} по рифме \textbf{k}, а также все переходы, ведущие в состояние \textbf{j} по рифме \textbf{k}. Требуется определить максимальный набор стихов, которые Вася может сочинить, используя свой автомат таким образом. После того, как какой-то переход стерт, он уже больше никогда в истории жизни этого автомата не будет восстановлен, так как Вася не хочет повторяться. \InputFile Первая строка входного файла содержит четыре целых числа -- количество состояний автомата \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{50}), количество рифм, которые использует Вася в своих стихах \textbf{K} (\textbf{1} ≤ \textbf{K} ≤ \textbf{50}), а также номера начального и конечного состояний \textbf{a} и \textbf{b} (\textbf{1} ≤ \textbf{a} ≠ \textbf{b} ≤ \textbf{N}). Вторая строка содержит одно целое число -- количество переходов в автомате \textbf{М} (\textbf{1} ≤ \textbf{М} ≤ \textbf{1000}). Далее следуют \textbf{М} строк, каждая из которых описывает один переход в формате \textbf{u_i}, \textbf{v_i}, \textbf{k_i}, означающий, что из состояния \textbf{u_i} можно перейти в состояние \textbf{v_i} по рифме \textbf{k_i}. \OutputFile В первой строке выходного файла выведите максимальное количество стихов \textbf{Z}, которые Вася может сочинить с помощью своего автомата. Далее выведите \textbf{Z} строк, по одной для каждого стиха. Описание стиха выводите в формате \textbf{s_\{1 \}k_1 s_2 k_2 … s_l_\{-1\} k_l_\{-1\} s_l} где \textbf{s_1} = \textbf{a}, \textbf{s_l} = \textbf{b}, \textbf{k_i} -- рифмы, по которым производится переход, а \textbf{S_i} -- состояния в порядке прохода.