题目描述

题目译自 XXXII Olimpiada Informatyczna – III etap Szpiedzy

在 Bajtocja 这个神秘国度，一支间谍组织正在执行 $m$ 种秘密任务。Bajtocja 由 $n$ 个城市组成，通过 $n-1$ 条道路连接，每条道路确保任意两城之间有唯一路径。第 $i$ 条道路连接城市 $a_i$ 和 $b_i$，由一名间谍驻守，当前执行任务 $x_i$，但可能有多名间谍执行同一任务。

你的职责是管理这些间谍的任务分配。面对突发的地缘政治变化，你决定将第 $i$ 条道路的间谍任务改为 $y_i$。为了确保任务安全，你通过特殊通讯方式向间谍传达指令。每个通讯是一组从 $1$ 到 $m$ 的排列，即包含原序列所有数字但顺序可能不同的序列。

发送通讯时，你会选择 Bajtocja 的部分城市，由友好居民在清晨挂出排列 $p$。当天，每名间谍会检查其负责道路两端的城市，若两城均挂出该排列，间谍将当前任务 $c_i$ 更换为 $p(c_i)$。当晚，居民会移除所有通讯内容。由于事态紧急，你希望尽量减少通讯次数。你的任务是设计一个通讯序列，高效实现任务变更目标。

输入格式

第一行包含两个整数 $n, m$ $(1 \leq n \leq 50000, 1 \leq m \leq 32)$，分别表示城市数量和任务种类数。

接下来的 $n-1$ 行，每行包含四个整数 $a_i, b_i, x_i, y_i$ $(1 \leq a_i, b_i \leq n, 1 \leq x_i, y_i \leq m)$，描述连接城市 $a_i$ 和 $b_i$ 的道路，驻守间谍当前执行任务 $x_i$，目标任务为 $y_i$。

输出格式

第一行输出一个非负整数 $k$，表示通讯次数。

接下来的 $k$ 行，每行描述一个通讯，包含排列 $p$ 和城市列表：即 $p(1), p(2), \ldots, p(m), l, v_1, v_2, \ldots, v_l$，以空格分隔，其中 $l$ 为城市数量，$v_1, \ldots, v_l$ 为互不相同的城市编号。若存在多组解，输出任意一种。

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

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, 3, 2, 4)$ 在所有城市 $(1, 2, 3, 4, 5, 6)$ 挂出，将全国的任务 $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, 2, 4, 3)$ 在城市 $(1, 4)$ 挂出，将道路 $1-4$ 的间谍任务从 $3$ 改为 $4$。

附加样例

1. $n=8, m=8$，$a_i = i+1, b_i = \left\lfloor \frac{i+1}{2} \right\rfloor, x_i = i, y_i = 1$。
2. $n=100, m=20$，$a_i = i, b_i = n, x_i = (i \bmod m) + 1, y_i = m$。
3. $n=1000, m=32$，$a_i = i+1, b_i = \left\lfloor \frac{i+1}{2} \right\rfloor, x_i = (i \bmod m) + 1, y_i = ((i+1) \bmod m) + 1$。
4. $n=50000, m=30$，$a_i = i, b_i = i+1, x_i = (i \bmod m) + 1, y_i = 1$。

数据范围与提示

为获得满分，你的代码需发送不超过 $10$ 次通讯。更多通讯次数可获得部分分，如下表所示：

详细子任务附加限制及分值如下表所示。