说明

小 F 在美术课上学习了如何画树。他画了一棵 $n$ 个结点的树 $T$，结点编号为 $1 \sim n$。

由于对当前这棵树不太满意，小 F 打算使用 $k$ 对一一配对的铅笔与橡皮来涂改它。初始时，他把每对铅笔与橡皮放置在树的某个结点上。具体地，对于 $1 \le i \le k$，记铅笔所在的结点为 $p_i$，橡皮所在的结点为 $e_i$，则初始时 $p_i = e_i$。在任意时刻，同一个结点上可以同时放置多支铅笔与多只橡皮。

每次涂改时，小 F 将首先选择一对铅笔与橡皮。设小 F 选择的是第 $t$ ($1 \le t \le k$) 对铅笔与橡皮，则他将按以下步骤进行涂改：

1. 选择任意一个结点 $x$ ($1 \le x \le n$)，将铅笔移动至结点 $x$，并绘制移动形成的边，即在 $p_t$ 与 $x$ 之间添加一条边，然后令 $p_t \leftarrow x$；
2. 选择一个与 $e_t$ 有边直接相连的结点 $y$ ($1 \le y \le n$)（可以是上一步中新绘制的边），将橡皮移动至结点 $y$，并擦除移动经过的边，即删除 $e_t$ 与 $y$ 之间的边，然后令 $e_t \leftarrow y$。

当然，小 F 需要保证每次涂改后得到的图仍然是一棵树。

小 F 希望使用尽可能少的铅笔与橡皮对将树 $T$ 涂改为另一棵树 $T'$。你需要帮助小 F 构造一组涂改的方案。具体地，你需要确定铅笔与橡皮对的数量 $k$，并且指定每对铅笔与橡皮的初始位置 $p_i, e_i$ ($1 \le i \le k, p_i = e_i$)，再构造一组涂改序列 $(t, x, y)$ ($1 \le t \le k, 1 \le x, y \le n$)，使得依次执行这些涂改后，树 $T$ 能被转变为树 $T'$。

【实现细节】

选手不需要，也不应该实现 main 函数。

选手需要确保提交的程序包含头文件 paint.h，即在程序开头加入以下代码：

#include "paint.h"

选手需要在提交的程序源文件 paint.cpp 中实现以下两个函数：

void init(int c, int t);

• $c, t$ 分别表示测试点编号与测试数据组数。$c = 0$ 表示该测试点为样例。
• 对于每个测试点，该函数会在程序开始运行时被交互库调用恰好一次。

void paint(int n, std::vector<int> u, std::vector<int> v);

• $n$ 表示树 $T$ 的结点个数。
• 对于 $0 \le i < n - 1$，$u_i, v_i$ 表示树 $T$ 的一条边。
• 对于 $n - 1 \le i < 2n - 2$，$u_i, v_i$ 表示树 $T'$ 的一条边。
• 对于每个测试点，该函数会被交互库调用恰好 $t$ 次。

选手可以通过调用以下函数设置铅笔与橡皮对的数量与每对铅笔与橡皮的初始位置：

void setting(int k, std::vector<int> p);

• $k$ 表示使用的铅笔与橡皮对的数量。选手需要保证 $0 \le k \le 2n$。
• 对于 $0 \le i < k$，$p_i$ 表示第 $i+1$ 对铅笔与橡皮的初始位置。选手需要保证 $p$ 的长度为 $k$，且对于所有 $0 \le i < k$，均有 $1 \le p_i \le n$。
• 选手需要保证交互库每次调用 paint 时，恰好调用了一次该函数。

选手可以通过调用以下函数进行一次涂改：

void alter(int t, int x, int y);

• $t, x, y$ 分别表示选择的铅笔与橡皮对的编号与结点的编号，具体含义如【题目描述】中所示。选手需要保证 $1 \le t \le k$，$1 \le x, y \le n$，且涂改后得到的图仍然是一棵树。
• 选手需要保证交互库每次调用 paint 时，调用该函数的次数不超过 $10^5$，且所有该函数的调用均在调用 setting 函数之后。

注意：在任何情况下，交互库运行所需时间均不会超过 $0.2$ 秒，所用内存为固定大小，且均不超过 $64$ MiB。

【测试程序方式】

试题目录下的 grader.cpp 是交互库参考实现，最终测试时所用的交互库实现与该参考实现有所不同，因此选手的解法不应该依赖交互库实现。

选手可以在本题目录下使用如下命令编译得到可执行程序：

g++ grader.cpp paint.cpp -o paint -O2 -std=c++14 -static

输入格式

对于编译得到的可执行程序：

• 可执行文件将从标准输入读入以下格式的数据：
  • 输入的第一行包含两个非负整数 $c, t$，分别表示测试点编号和测试数据组数。
  • 接下来依次为每组测试数据，对于每组测试数据：
    • 第一行包含一个正整数 $n$，表示树 $T$ 的结点个数。
    • 第 $i+1$ ($1 \le i \le n-1$) 行包含两个正整数 $u_i, v_i$，表示树 $T$ 的一条边。
    • 第 $i+n$ ($1 \le i \le n-1$) 行包含两个正整数 $u'_i, v'_i$，表示树 $T'$ 的一条边。

输出格式

• 可执行文件将输出以下格式的数据至标准输出：
  • 对于每组测试数据：
    • 第一行包含两个非负整数 $k, m$，分别表示使用的铅笔与橡皮对的数量与涂改序列的长度。
    • 第二行包含 $k$ 个正整数 $p_1, p_2, \dots, p_k$，分别表示每对铅笔与橡皮的初始位置。
    • 第 $i+2$ ($1 \le i \le m$) 行包含三个正整数 $t, x, y$，分别表示第 $i$ 次涂改选择的铅笔与橡皮对的编号与结点的编号。

0 2
5
2 3
3 1
5 1
5 4
1 4
2 3
3 1
5 3
5
4 2
1 3
5 1
1 2
2 1
3 5
3 1
4 5

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

提示

【样例 1 解释】

该样例共包含两组测试数据。

对于第一组测试数据，树 $T$ 包含边 $\{(1,3), (3,2), (1,5), (5,4)\}$，树 $T'$ 包含边 $\{(1,4), (2,3), (3,1), (5,3)\}$。一种可行的涂改方案如下：

• 初始时，共有 1 对铅笔与橡皮放置在结点 1。
• 第一次涂改选择 $x = 4$，$y = 5$，添加边 $(1,4)$，删除边 $(1,5)$，得到的树包含边 $\{(1,3), (3,2), (5,4), (1,4)\}$，此时 $p_1 = 4$，$e_1 = 5$；
• 第二次涂改选择 $x = 5$，$y = 4$，添加边 $(4,5)$，删除边 $(4,5)$，此时 $p_1 = 5$，$e_1 = 4$；
• 第三次涂改选择 $x = 3$，$y = 5$，添加边 $(5,3)$，删除边 $(4,5)$，得到的树包含边 $\{(1,3), (3,2), (1,4), (5,3)\}$，即为树 $T'$。

【下发文件说明】

在本试题目录下：

1. grader.cpp 是提供的交互库参考实现。
2. paint.h 是头文件，选手不用关心具体内容。
3. template_paint.cpp 是提供的示例代码，选手可参考并实现自己的代码。

选手注意对所有下发文件做好备份。最终评测时只测试本试题目录下的 paint.cpp，对该程序以外文件的修改不会影响评测结果。

【数据范围】

对于所有测试数据，均有：

• $1 \le t \le 10$；
• $4 \le n \le 200$；
• 对于所有 $1 \le i < n$，均有 $1 \le u_i, v_i \le n$，且所有的边构成了一棵树；
• 对于所有 $1 \le i < n$，均有 $1 \le u'_i, v'_i \le n$，且所有的边构成了一棵树；
• $T$ 和 $T'$ 均在所有 $n$ 个结点的树中独立均匀随机生成。

::cute-table{tuack}

测试点编号	分值	$n =$
$1$	$14$	$4$
$2$	$23$	$20$
$3$	$26$	$50$
$4$	$37$	$200$

【评分方式】

注意：

• 选手不应当通过非法方式获取交互库的内部信息，如直接与标准输入、输出流进行交互。此类行为将被视为作弊；
• 最终的评测交互库与样例交互库的实现不同。

本题首先会受到和传统题相同的限制，例如编译错误会导致整道题目得 $0$ 分，运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 $0$ 分等。选手只能在程序中访问自己定义的变量以及交互库给出的变量，尝试访问其他地址空间将可能导致编译错误或运行错误。

每次调用 paint 函数时，若 setting 函数或 alter 函数调用不合法，或 alter 函数调用次数超过 $10^5$，则相应测试点得 $0$ 分。

在上述条件基础上：

• 在测试点 $1$ 和测试点 $2$ 中，程序得到满分当且仅当每次调用 paint 函数返回时树 $T$ 均被转变为树 $T'$。
• 在测试点 $3$ 中，对于每组测试数据，设 $k_{\min}$ 表示使用的铅笔与橡皮对数的最小值，
  • 若 paint 函数返回时树 $T$ 未被转变为树 $T'$，则获得 $0$ 分；
  • 否则，获得 $\lfloor 26 \cdot 0.97^{k - k_{\min}} \rfloor$ 分。

程序得到的分数为所有测试数据的得分的最小值。

• 在测试点 $4$ 中，对于每组测试数据，设 $k_{\min}$ 表示使用的铅笔与橡皮对数的最小值，
  • 若 $k \ne k_{\min}$，则获得 $0$ 分；
  • 否则，若 paint 函数返回时树 $T$ 未被转变为树 $T'$，则获得 $4$ 分；
  • 否则，获得 $\lfloor 4 + 33 \cdot 0.99^{\max(\lfloor m / 2000 \rfloor - 5, 0)} \rfloor$ 分。

程序得到的分数为所有测试数据的得分的最小值。