1001. Grand Mex

题目描述

完整题目参见：PDF 题面

有 $n$ 个整数 $a_1,a_2, \ldots ,a_ n$，初始时它们全部等于 $0$。

接下来依次进行 $n-1$ 次操作。第 $i$ 次操作给出两个不同的下标 $x_i,y_i$。你需要选择其中一个下标。

如果选择 $x_i$，则执行

$$a_{x_i}\leftarrow a_{x_i}+1,\qquad a_{y_i}\leftarrow 0.$$

如果选择 $y_i$，则执行

$$a_{y_i}\leftarrow a_{y_i}+1,\qquad a_{x_i}\leftarrow 0.$$

保证将所有 $\lparen x_i,y_i \rparen$ 看作无向边后，它们构成一棵包含 $n$ 个点的树。

你必须按照输入顺序完成全部操作。请最小化最终序列 $a$ 的 $\operatorname{mex}$，并构造一种达到最小值的操作方案。

序列的 $\operatorname{mex}$ 定义为没有在序列中出现的最小非负整数。例如，$\operatorname{mex}([0,2,2])=1$。

输入格式

第一行包含一个整数 $T$（$1\le T\le 2\times 10^5$），表示测试数据的组数。

对于每组测试数据：

• 第一行包含一个整数 $n$（$2\le n\le 5\times 10^5$）。

• 接下来 $n-1$ 行，第 $i$ 行包含两个整数 $x_i,y_i$（$1\le x_i,y_i\le n$，$x_i\ne y_i$），表示第 $i$ 次操作涉及的两个下标。

保证每组测试数据中的所有边构成一棵树，且对于所有测试数据 $\sum n \le 10^6$。

输出格式

对于每组测试数据：

第一行输出一个整数，表示最终序列的最小可能 $\operatorname{mex}$。

第二行输出 $n-1$ 个整数 $s_1,s_2,\ldots,s_{n-1}$。其中 $s_i$ 必须等于 $x_i$ 或 $y_i$，表示在第 $i$ 次操作中选择 $a_{s_i}$ 加一，并将另一个数清零。

如果存在多种最优方案，输出任意一种。

样例输入

3
2
1 2
6
4 3
2 1
3 1
5 3
6 1
8
4 7
2 5
1 3
6 2
3 6
8 3
2 4

样例输出

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

提示

样例输出分别给出了一种最优操作方案。可能存在其他正确的最优方案。

来源：2026杭电多校-测试专用（山西实验） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1234&pid=1001 ⚠ 本题为 Special Judge。官方数据中的 .out 多为评测机判定输出（如 AC/OK/Correct/yes），导入后需自行提供 checker 方可正确评测。