Poet#2078
Aspiring poet Vasya has designed a finite automaton to streamline his poem-writing process. This automaton consists of states, with transitions between these states facilitated by different rhymes. The automaton features a single initial state and a single final state . 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 poems from becoming monotonous, Vasya modifies the automaton after each transition. Specifically, when a transition occurs from state to state using rhyme , Vasya removes all transitions that originate from state via rhyme , as well as all transitions that lead to state via rhyme .
Your task is to determine the maximum number of poems Vasya can generate using his automaton under these conditions. Once a transition is removed, it can never be restored during the automaton's operation, as Vasya wants to avoid repetition.
The first line of the input contains four integers: the number of states in the automaton (1 \leq N \leq 50), the number of rhymes (1 \leq K \leq 50), and the indices of the initial and final states and (1 \leq a \neq b \leq N). The second line contains one integer: the number of transitions in the automaton (1 \leq M \leq 1000). Each of the following 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.
On the first line of the output, print the maximum number of poems that Vasya can create with his automaton. Then, print lines, each representing a poem. Each poem should be described in the format:
s_1\ k_1\ s_2\ k_2\ \ldots\ 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.
Example 1