← 返回题目列表

Codeforces · 2218/F

F. 第67棵树问题

中文机器翻译题面 查看原题

现在 PMOI 赛季已经结束(克劳德获胜),猕猴可以继续他的启蒙之旅。他要解决的问题越来越难,前世的负担越来越重,你正在以如此快的速度失去自由意志,以至于你很难记住上次你在不受猕猴强迫的情况下凭自己的意志做任何事情是什么时候。对你来说唯一的好处是,一旦你为猕猴解决了以下问题,猕猴就会免费带你参观他目前在树上的栖息地。

给你两个整数 $$$x$$$ 和 $$$y$$$。

您的任务是构造一棵具有 $$$x + y$$$ 节点的树,以节点 $$$1$$$ 为根,这样:

  • 树中恰好有 $$$x$$$ 个节点 甚至 子树$$$^{\text{*}}$$$ 大小。
  • 树中恰好有 $$$y$$$ 个节点 奇数 子树大小。
如果存在多个有效树,则可以输出其中任何一个。如果不存在这样的树,则输出 NO.

$$$^{\text{*}}$$$顶点 $$$u$$$ 的子树是在到根的简单路径上经过 $$$u$$$ 的所有顶点的集合(包括 $$$u$$$ 本身)。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

随后的每一行包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$0 \leq x, y \leq 2 \cdot 10^5$$$, $$$1 \leq x + y \leq 2 \cdot 10^5$$$)。

保证所有测试用例的 $$$x+y$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个查询,输出“是“或”NO”,取决于构造是否存在。可以输出“是“和”NO“在任何情况下(例如,”是", "是的“,和”是“将被识别为肯定响应)。

如果输出“是”,输出$$$x+y-1$$$行,每行包含两个空格分隔的整数$$$u$$$和$$$v$$$,表示节点$$$u$$$和$$$v$$$之间有一条边。

示例

输入
复制

7
1 1
2 1
0 3
3 4
0 2
1 0
4 7

输出
复制

YES
1 2
NO
YES
1 2
1 3
YES
1 2
2 3
3 4
4 5
5 6
6 7
NO
NO
YES
1 2
2 3
3 4
4 5
4 11
2 6
6 7
7 8
2 9
9 10

注意

在第一个测试中,输出树有效,因为节点 $$$1$$$ 的子树大小为 $$$2$$$,为偶数,而节点 $$$2$$$ 的子树大小为 $$$1$$$,为奇数。

在第二个测试中,可以表明不存在有效的树。

在第四个测试中,子树大小为偶数的节点为$$$[2, 4, 6]$$$,子树大小为奇数的节点为$$$[1, 3, 5, 7]$$$。

最终测试的输出如下图所示,其中蓝色节点具有偶数子树大小,红色节点具有奇数子树大小。