In Byteotia, there is a group of spies, each of whom performs exactly one of $m$ missions. There are $n$ cities in Byteotia connected by $n-1$ roads. There is exactly one path between any two cities. The $i$-th road connects cities $a_i$ and $b_i$, and there is a spy stationed there who is currently performing mission $x_i$. One mission can be performed by multiple spies.

Your job is to manage which mission each spy performs. Due to a sudden change in the geopolitical situation, you have decided that the spy working on road $i$ should now perform mission $y_i$.

Since mission security is paramount, you will transmit this information to the spies using special messages. A single message is a permutation of numbers from $1$ to $m$, where a permutation of a sequence is any sequence containing the same numbers as the original, but potentially in a different order.

To transmit a given message to the spies, you will choose a subset of Byteotian cities where friendly residents will display the given permutation $p$ in the morning. On the same day, every spy will visit both cities connected by the road where they work, and they will change their mission if and only if the permutation was displayed in both cities. Then, in the evening, the same friendly residents will remove the displayed messages.

If the current mission performed by the $i$-th spy is $c_i$, then after the change, they will perform mission $p(c_i)$. The matter is urgent, so you want the number of messages sent to be small. Your task is to design a sequence of messages that allows you to achieve your goal.

Input

The first line of input contains two integers $n$ and $m$ ($1 \le n \le 50\,000$, $1 \le m \le 32$), representing the number of cities in Byteotia and the number of missions, respectively. Each of the next $n-1$ lines contains four integers $a_i, b_i, x_i, y_i$ ($1 \le a_i, b_i \le n$, $1 \le x_i, y_i \le m$), describing the road from $a_i$ to $b_i$, where the spy currently performs mission $x_i$ and should perform mission $y_i$.

Output

In the first line of output, print a single non-negative integer $k$ representing the number of messages. Then, print the descriptions of these $k$ messages. The description of a message with permutation $p$ announced in $l$ cities $v_1, \dots, v_l$ is a sequence of integers $p(1), p(2), \dots, p(m), l, v_1, v_2, \dots, v_l$ separated by single spaces. The numbers $v_1, \dots, v_l$ must be pairwise distinct. If there are multiple valid sequences of messages, print any one of them.

Examples

Input 1

6 4
3 1 1 3
1 2 3 2
4 1 2 4
3 5 3 1
6 3 2 2

Output 1

3
1 3 2 4 6 1 2 3 4 5 6
3 1 2 4 4 1 6 5 3
1 2 4 3 2 1 4

Note 1

Explanation of the example: The first permutation $(1, 3, 2, 4)$ is displayed in all cities, so in all of Byteotia we change all missions $2$ to $3$, and $3$ to $2$. The second permutation $(3, 1, 2, 4)$ is displayed in cities $1, 6, 5$, and $3$. It changes the mission of the spy on road $1-3$ from $1$ to $3$, the spy on road $3-5$ from $2$ to $1$, and the spy on road $3-6$ from $3$ to $2$. With the last permutation, we change the mission of the spy on road $1-4$ from $3$ to $4$.

Sample tests

Test 0 is the example above. Additionally:

1ocen: $n = 8, m = 8, a_i = i + 1, b_i = \lfloor \frac{i+1}{2} \rfloor, x_i = i, y_i = 1$. 2ocen: $n = 100, m = 20, a_i = i, b_i = n, x_i = (i \pmod m) + 1, y_i = m$. 3ocen: $n = 1000, m = 32, a_i = i + 1, b_i = \lfloor \frac{i+1}{2} \rfloor, x_i = (i \pmod m) + 1, y_i = ((i + 1) \pmod m) + 1$. 4ocen: $n = 50\,000, m = 30, a_i = i, b_i = i + 1, x_i = (i \pmod m) + 1, y_i = 1$.

Evaluation

The test set is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups.

To receive full points for a given subtask, your solution must send no more than $10$ messages. It is also possible to receive partial points for a larger number of messages, as described in the table below.