Poet
Aspiring poet Vasya has designed a finite automaton to streamline his poem-writing process. This automaton consists of N states, with transitions between these states facilitated by K different rhymes. The automaton features a single initial state a and a single final state b. The outcome of Vasya's creative process is a sequence of rhymes that the automaton accepts, to which he then applies pre-written verses.
To prevent the poems from becoming repetitive, Vasya modifies the automaton after each transition. Specifically, when a transition occurs from state i to state j using rhyme k, Vasya removes all transitions that originate from state i via rhyme k, as well as all transitions that lead to state j via rhyme k.
Your task is to determine the maximum number of distinct poems Vasya can generate using his automaton under these conditions. Once a transition is removed, it cannot be restored during the automaton's operation, as Vasya aims to avoid repetition.
Input
The first line of the input contains four integers: the number of states in the automaton N (1 ≤ N ≤ 50), the number of rhymes K (1 ≤ K ≤ 50), and the indices of the initial and final states a and b (1 ≤ a ≠ b ≤ N). The second line contains one integer: the number of transitions in the automaton M (1 ≤ M ≤ 1000). Each of the following M lines describes a transition in the format u_i, v_i, k_i, indicating a transition from state u_i to state v_i using rhyme k_i.
Output
On the first line of the output, print the maximum number of poems Z that Vasya can create with his automaton. Then, print Z lines, each representing a poem. Each poem should be described in the format:
s_{1}k_1 s_2 k_2 … s_l_{-1} k_l_{-1} s_l
where s_1 = a, s_l = b, k_i are the rhymes used for transitions, and S_i are the states in the order they are traversed.