← 返回题目列表

Codeforces · 1196/E

E. 棋盘上的连接组件

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

给你两个整数 $$$b$$$ 和 $$$w$$$。您有一个大小为 $$$10^9 \times 10^9$$$ 的棋盘,左上角的单元格位于 $$$(1; 1)$$$,单元格 $$$(1; 1)$$$ 被漆成白色。

你的任务是在这个棋盘上找到一个连通分量,其中恰好包含 $$$b$$$ 黑色单元格和 $$$w$$$ 白色单元格。如果两个单元格共享一条边,则称它们为连通单元格(即,对于单元格 $$$(x, y)$$$,最多有四个连通单元格:$$$(x - 1, y)、(x + 1, y)、(x, y - 1)、(x, y + 1)$$$)。如果对于该组中的每对单元格 $$$C_1$$$ 和 $$$C_2$$$,存在一个单元格序列 $$$c_1$$$、$$$c_2$$$、...、$$$c_k$$$,使得 $$$c_1 = C_1$$$、$$$c_k = C_2$$$,所有 $$$c_i$$$ 来自$$$1$$$ 到 $$$k$$$ 属于这组单元,并且对于 [1, k - 1]$$$ 中的每个 $$$i \in,单元 $$$c_i$$$ 和 $$$c_{i + 1}$$$ 是相连的。

显然,不可能找到这样的组件。在这种情况下打印“NO”。否则,打印“YES”和任何合适的连接组件。

您必须回答 $$$q$$$ 独立查询。

输入

输入的第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 10^5$$$) — 查询数。然后是 $$$q$$$ 查询。

查询的唯一行包含两个整数 $$$b$$$ 和 $$$w$$$ ($$$1 \le b, w \le 10^5$$$) — 所需的黑色单元格数量和所需的白色单元格数量。

保证单元格数量之和不超过 $$$2 \cdot 10^5$$$ ($$$\sum w + \sum b \le 2 \cdot 10^5$$$)。

输出

对于每个查询,打印其答案。

如果无法找到所需的组件,则在第一行打印“NO”。

否则,在第一行打印“YES”。在接下来的 $$$b + w$$$ 行中,以任意顺序打印组件单元格的坐标。您的答案中应该恰好有 $$$b$$$ 黑色单元格和 $$$w$$$ 白色单元格。应连接印刷组件。

如果有多个答案,您可以打印任何答案。答案中的所有坐标都应在 $$$[1; 范围内10^9]$$$。

示例

输入 #1

3
1 1
1 4
2 5

输出 #1

YES
2 2
1 2
YES
2 3
1 3
3 3
2 2
2 4
YES
2 3
2 4
2 5
1 3
1 5
3 3
3 5