← 返回题目列表

Codeforces · 1819/B

B. 屠夫

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

安东为他最喜欢的英雄——屠夫玩了他最喜欢的游戏“远古保卫战 2”。现在他想自己做晚饭。为此,他将选取一个高度为 $$$h$$$ 和宽度为 $$$w$$$ 的矩形,然后进行垂直或水平切割,以使所得的两个部分都有整数边。之后,他会将其中一个零件放入盒子中,然后再次切割另一个零件,以此类推。

更正式地说,一个尺寸为 $$$h \times w$$$ 的矩形可以被切割成尺寸为 $$$x \times w$$$ 和 $$$(h - x) \times w$$$ 的两部分,其中 $$$x$$$ 是从 $$$1$$$ 到 $$$(h - 1)$$$ 的整数,或者切割成尺寸为 $$$h \times y$$$ 和 $$$h \times y$$$ 的两部分$$$h \times (w - y)$$$,其中 $$$y$$$ 是从 $$$1$$$ 到 $$$(w - 1)$$$ 的整数。

他会重复这个操作$$$n - 1$$$次,然后把剩下的矩形也放进盒子里。因此,盒子将包含 $$$n$$$ 个矩形,其中 $$$n - 1$$$ 个矩形因切割而被放入盒子中,第 $$$n$$$ 个矩形是屠夫在所有 $$$n - 1$$$ 切割后留下的矩形。

不幸的是,Butcher 忘记了数字 $$$h$$$ 和 $$$w$$$,但他仍然有 $$$n$$$ 矩形以随机顺序混合。请注意,Butcher 并没有旋转矩形,而只是将它们打乱。现在他想知道可以从中获得这组矩形的所有可能对 $$$(h, w)$$$。而你必须帮助他做到这一点!

保证至少存在一对 $$$(h, w)$$$ 可以从中获得这组矩形。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 获得的矩形数量。

接下来的 $$$n$$$ 行的第 $$$i$$$ 行包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i, b_i \le 10^6$$$) — 第 $$$i$$$ 个矩形的高度和宽度。

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

输出

对于每个测试用例,在第一行输出一个整数 $$$m$$$ — 对的数量 $$$(h, w)$$$ 表示可以从中获得给定矩形的矩形的大小。如果两个矩形具有不同的高度或宽度,则认为它们是不同的。

在下面的每一行 $$$m$$$ 上打印输出整数 $$$h_i$$$ 和 $$$w_i$$$ - 可以从中获取给定矩形的矩形的高度和宽度。您可以按任何顺序输出矩形。

示例

输入 #1

4
3
1 2
3 5
1 3
3
1 1
1 1
1 1
1
10 10
4
3 2
5 5
2 2
8 7

输出 #1

1
4 5
2
1 3
3 1
1
10 10
1
13 7

注意

在第一个测试用例中,Butcher 只能有一个大小为 $$$4 \times 5$$$ 的矩形。然后切口可能如下所示(首先进行绿色切口,然后进行红色切口):

在第二个测试用例中,Butcher 可以有一个 $$$1 \times 3$$$ 或 $$$3 \times 1$$$ 的矩形。切口看起来像这样(首先进行绿色切口,然后进行红色切口):

在第三个测试用例中,Butcher 没有进行任何切割,因此矩形为 $$$10 \times 10$$$。