← 返回题目列表

Codeforces · 2046/E1

E1. 胡夫和比赛(简单版)

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

这是问题的简单版本。版本之间的差异在于,在此版本中,$$$m$$$ 等于$$$2$$$。只有解决了该问题的所有版本,您才能破解。

古埃及有一场解决问题的竞赛,参与者有 $$$n$$$,编号从 $$$1$$$ 到 $$$n$$$。每个参与者都来自某个城市;城市编号从 $$$1$$$ 到 $$$m$$$。每个城市至少有一名参与者。

第 $$$i$$$ 个参与者拥有实力 $$$a_i$$$、专业化 $$$s_i$$$ 和智慧 $$$b_i$$$,因此 $$$b_i \ge a_i$$$。比赛中的每个问题都有一个难度 $$$d$$$ 和一个独特的主题 $$$t$$$。如果满足以下条件,第 $$$i$$$ 个参与者将解决该问题:

- $$$a_i \ge d$$$,即它们的强度不小于问题的难度,或者
- $$$s_i = t$$$ 和 $$$b_i \ge d$$$,即他们的专业与问题的主题相匹配,他们的智慧不低于问题的难度。

Cheops 希望以这样的方式选择问题,即对于所有 $$$i < j$$$,来自城市 $$$i$$$ 的每个参与者将比来自城市 $$$j$$$ 的每个参与者解决严格更多的问题。

请找到一组最多 $$$5n$$$ 问题,其中所有问题的主题都明确,从而满足 Cheops 的意愿,或者说明这是不可能的。

输入

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

每个测试用例的第一行包含两个整数 $$$n$$$、$$$m$$$ ($$$2 \mathbf{=} m \le n \le 3 \cdot {10}^5$$$) – 参与者数量和城市数量。

以下 $$$n$$$ 行描述了参与者。第 $$$i$$$ 行包含三个整数 —$$$a_i$$$、$$$b_i$$$、$$$s_i$$$ ($$$0 \le a_i, b_i, s_i \le {10}^9$$$, $$$a_i \le b_i$$$) — 分别是第 $$$i$$$ 参与者的力量、智慧和专业化。

接下来的 $$$m$$$ 行描述了城市。在第 $$$i$$$ 行中,第一个数字是整数 $$$k_i$$$ ($$$1 \le k_i \le n$$$) — 来自第 $$$i$$$ 个城市的参与者数量。其后是 $$$k_i$$$ 整数 $$$q_{i, 1}, q_{i, 2}, \ldots, q_{i, k_i}$$$ — ($$$1 \le q_{i, j} \le n$$$, $$$1 \le j \le k_i$$$) — 来自该城市的参与者的指数。保证每个参与者只被提及一次。

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

输出

对于每个测试用例,如果存在一组满足 Cheops 条件的问题,则在第一行输出一个整数 $$$p$$$ ($$$1 \le p \le 5n$$$) — 解决方案中的问题数。

然后输出 $$$p$$$ 行,每行包含两个整数 $$$d$$$ 和 $$$t$$$ ($$$0 \le d, t \le {10}^9$$$) - 相应问题的难度和主题。主题必须鲜明。

如果没有一组问题满足 Cheops 的愿望,则打印 $$$-1$$$ 。

示例

输入 #1

2
5 2
5 7 1
6 7 2
3 9 2
5 10 3
4 4 1
2 1 2
3 3 4 5
2 2
1 2 1
1 2 1
1 2
1 1

输出 #1

7
6 4
6 5
5 6
5 7
4 8
4 9
7 1
-1