1s 1G
在洛谷上提交时，请使用不低于 C++17 的语言版本，并且无需添加 paint.h 头文件。但是，应当添加以下内容：
void setting(int k, std::vector<int> p);
void alter(int t, int x, int y);
小 F 在美术课上学习了如何画树。他画了一棵 个结点的树 ，结点编号为 。
由于对当前这棵树不太满意，小 F 打算使用 对一一配对的铅笔与橡皮来涂改它。初始时，他把每对铅笔与橡皮放置在树的某个结点上。具体地，对于 ，记铅笔所在的结点为 ，橡皮所在的结点为 ，则初始时 。在任意时刻，同一个结点上可以同时放置多支铅笔与多只橡皮。
每次涂改时，小 F 将首先选择一对铅笔与橡皮。设小 F 选择的是第 () 对铅笔与橡皮，则他将按以下步骤进行涂改：
- 选择任意一个结点 ()，将铅笔移动至结点 ，并绘制移动形成的边，即在 与 之间添加一条边，然后令 ；
- 选择一个与 有边直接相连的结点 ()（可以是上一步中新绘制的边），将橡皮移动至结点 ，并擦除移动经过的边，即删除 与 之间的边，然后令 。
当然，小 F 需要保证每次涂改后得到的图仍然是一棵树。
小 F 希望使用尽可能少的铅笔与橡皮对将树 涂改为另一棵树 。你需要帮助小 F 构造一组涂改的方案。具体地，你需要确定铅笔与橡皮对的数量 ，并且指定每对铅笔与橡皮的初始位置 ()，再构造一组涂改序列 ()，使得依次执行这些涂改后，树 能被转变为树 。
【实现细节】
选手不需要，也不应该实现 main 函数。
选手需要确保提交的程序包含头文件 paint.h，即在程序开头加入以下代码：
选手需要在提交的程序源文件 paint.cpp 中实现以下两个函数：
- 分别表示测试点编号与测试数据组数。 表示该测试点为样例。
- 对于每个测试点，该函数会在程序开始运行时被交互库调用恰好一次。
void paint(int n, std::vector<int> u, std::vector<int> v);
- 表示树 的结点个数。
- 对于 ， 表示树 的一条边。
- 对于 ， 表示树 的一条边。
- 对于每个测试点，该函数会被交互库调用恰好 次。
选手可以通过调用以下函数设置铅笔与橡皮对的数量与每对铅笔与橡皮的初始位置：
void setting(int k, std::vector<int> p);
- 表示使用的铅笔与橡皮对的数量。选手需要保证 。
- 对于 ， 表示第 对铅笔与橡皮的初始位置。选手需要保证 的长度为 ，且对于所有 ，均有 。
- 选手需要保证交互库每次调用
paint 时，恰好调用了一次该函数。
选手可以通过调用以下函数进行一次涂改：
void alter(int t, int x, int y);
- 分别表示选择的铅笔与橡皮对的编号与结点的编号，具体含义如【题目描述】中所示。选手需要保证 ，，且涂改后得到的图仍然是一棵树。
- 选手需要保证交互库每次调用
paint 时，调用该函数的次数不超过 ，且所有该函数的调用均在调用 setting 函数之后。
注意：在任何情况下，交互库运行所需时间均不会超过 秒，所用内存为固定大小，且均不超过 MiB。
【测试程序方式】
试题目录下的 grader.cpp 是交互库参考实现，最终测试时所用的交互库实现与该参考实现有所不同，因此选手的解法不应该依赖交互库实现。
选手可以在本题目录下使用如下命令编译得到可执行程序：
g++ grader.cpp paint.cpp -o paint -O2 -std=c++14 -static
