logo AlgoBeat OnlineJudge
登录 注册

#214764. 西安之泪

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

2025 年 9 月至 10 月期间,断断续续的雨笼罩了西安 30 余天。

Voidina 看着空中飘落的如烟小雨,开始了遐想。


给定一颗无根树,共有 个顶点。每个顶点 都具有一个点权 ,初始所有点权都为

你可以进行如下的操作最多不超过 次:

  • 指定顶点的编号 ,使得这棵树暂时以顶点 为根,随后对于顶点 的子树中的每一个顶点 ,将其点权修改为 。此处的 表示按位异或

如图,当取 进行操作时,顶点 的点权会分别被异或上

请你构造一个满足上述要求的操作序列,使得最终对于树中的每个顶点 ,都满足

对于两个非负整数 ,它们的按位异或是指,将它们作为二进制数,对二进制表示中的每一位进行如下运算得到的结果:

  • 的这一位上不同时,结果的这一位为
  • 的这一位上相同时,结果的这一位为

比如,

输入格式

本题有多组数据。第一行一个正整数 ,表示数据组数。

对于每组数据:

第一行一个整数 ,表示树的顶点数。

接下来 行,每行两个整数 ,表示树中的一条边。

保证 组数据中 的和不超过

输出格式

对于每组数据:

第一行一个整数 ,代表你所构造的操作序列中操作的次数。

接下来 行,每行两个整数 ,具体含义见题目描述。

样例

样例输入 1

1
2
1 2

样例输出 1

2
1 2
2 1