F. The 67th Tree Problem

    传统题 4000ms 256MiB

The 67th Tree Problem

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem Description

既然 PMOI 赛季已经结束(Cloud 获胜),Macaque 可以继续他的悟道之旅。他要解决的问题越来越难,前世的重担越来越沉,而你正在以如此快的速度丧失自由意志,以至于你很难记起上一次出于自己意愿而非被 Macaque 强迫去做任何事情是什么时候。对你来说唯一的好处是,一旦你为他解决了以下问题,Macaque 将带你免费参观他目前在树上栖息的地方。

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

你的任务是构造一棵有 $x + y$ 个节点的树,以节点 $1$ 为根,满足:

  • 恰好有 $x$ 个节点的子树$^{\text{∗}}$ 大小为偶数。
  • 恰好有 $y$ 个节点的子树大小为奇数。
如果存在多棵合法的树,你可以输出其中任意一棵。如果不存在这样的树,输出 NO。

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

Input Format

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

Output Format

对于每个查询,输出 "YES" 或 "NO",取决于是否存在合法的构造。你可以以任意大小写形式输出 "YES" 和 "NO"(例如,"yES"、"yes" 和 "Yes" 都会被识别为肯定回答)。

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

Examples

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

Note

在第一个测试中,输出的树是合法的,因为节点 $1$ 的子树大小为 $2$,是偶数;节点 $2$ 的子树大小为 $1$,是奇数。

在第二个测试中,可以证明不存在合法的树。

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

最后一个测试的输出如下图所示,其中蓝色节点的子树大小为偶数,红色节点的子树大小为奇数。

Source

Imported from Codeforces — Codeforces Round 1090 (Div. 4).

Codeforces Round 1090 (Div. 4)

未参加
状态
已结束
规则
XCPC
题目
7
开始于
2026-11-11 15:00
结束于
2026-11-11 17:30
持续时间
2.5 小时
主持人
参赛人数
14