在拜特国（Bajtocja）有一个间谍组织，每位间谍负责执行 $m$ 个任务中的恰好一个。拜特国有 $n$ 个城市，由 $n-1$ 条道路连接，任意两个城市之间有且仅有一条路径。第 $i$ 条道路连接城市 $a_i$ 和 $b_i$，且有一名间谍在此工作，目前正在执行任务 $x_i$。

一个任务可以由多名间谍同时执行。

你的工作是管理每位间谍执行的任务。由于地缘政治局势的突然变化，你决定让在第 $i$ 条道路工作的间谍现在执行任务 $y_i$。

由于任务安全至关重要，你将通过特殊通信向间谍传达这些信息。单次通信是一个 $1$ 到 $m$ 的数字排列，其中排列是指包含与原序列相同数字但顺序可能不同的序列。

为了传达给定的通信，你将选择拜特国的一个城市子集，友好的居民会在清晨在这些城市挂出给定的排列 $p$。当天，每位间谍都会访问其工作道路连接的两个城市，并且仅当两个城市都挂出了该排列时，才会更改其任务。随后，傍晚时分，同一批友好的居民会撤下挂出的通信。

如果第 $i$ 位间谍当前执行的任务是 $c_i$，那么在更改后，他将执行任务 $p(c_i)$。情况紧急，因此你希望发送的通信数量尽可能少。你的任务是设计一个通信序列，以实现你的目标。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 50\,000, 1 \le m \le 32$)，分别表示拜特国的城市数量和任务数量。接下来的 $n-1$ 行，每行包含四个整数 $a_i, b_i, x_i, y_i$ ($1 \le a_i, b_i \le n, 1 \le x_i, y_i \le m$)，描述了连接 $a_i$ 和 $b_i$ 的道路，以及在该道路工作的间谍当前执行的任务 $x_i$ 和应执行的任务 $y_i$。

输出格式

在输出的第一行，输出一个非负整数 $k$，表示通信的数量。接下来输出这 $k$ 个通信的描述。对于包含排列 $p$ 并在 $l$ 个城市 $v_1, \dots, v_l$ 中宣布的通信，其描述为整数序列 $p(1), p(2), \dots, p(m), l, v_1, v_2, \dots, v_l$，各数字之间用空格分隔。数字 $v_1, \dots, v_l$ 必须互不相同。如果存在多个合法的通信序列，输出其中任意一个即可。

样例

输入 1

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

输出 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

说明 1

样例解释：我们将第一个排列 $(1, 3, 2, 4)$ 挂在所有城市，因此在整个拜特国，我们将所有任务 $2$ 变为 $3$，将 $3$ 变为 $2$。我们将第二个排列 $(3, 1, 2, 4)$ 挂在城市 $1, 6, 5$ 和 $3$。它将道路 $1-3$ 上的间谍任务从 $1$ 变为 $3$，道路 $3-5$ 上的间谍任务从 $2$ 变为 $1$，道路 $3-6$ 上的间谍任务从 $3$ 变为 $2$。最后，我们用第三个排列将道路 $1-4$ 上的间谍任务从 $3$ 变为 $4$。

子任务

测试集分为以下子任务。每个子任务的测试用例由一组或多组独立的测试组成。

为了获得给定子任务的满分，你的解决方案发送的通信数量不得超过 $10$ 次。通过发送更多通信获得部分分也是可能的，如下表所示：