← 返回题目列表

Codeforces · 1468/M

M. 类似套装

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

给你 $$$n$$$ 组整数。第 $$$i$$$ 组包含 $$$k_i$$$ 个整数。

如果两个集合共享至少两个共同元素,则称它们相似。 e.存在两个整数 $$$x$$$ 和 $$$y$$$ 使得 $$$x \ne y$$$ ,并且它们都属于这两个集合中的每一个。

你的任务是在给定的集合中找到两个相似的集合,或者报告不存在这样的集合对。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 50000$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$) 给定集合的数量。以下 $$$n$$$ 行描述了这些集合。第 $$$i$$$ 行以整数 $$$k_i$$$ 开头 ($$$2 \le k_i \le 10^5$$$) — 第 $$$i$$$ 集合中整数的数量。然后是 $$$k_i$$$ 整数 $$$a_{i,1}$$$, $$$a_{i,2}$$$, ..., $$$a_{i,k_i}$$$ ($$$1 \le a_{i,j} \le 10^9$$$) — 第 $$$i$$$ 集合的元素。保证每个集合中的所有元素都是不同的。

所有测试用例中所有集合中的元素总数不大于 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,将答案打印在一行上。

如果没有一对相似的集合,则打印 -1。

否则,打印两个不同的整数——相似集合的索引。这些集合按照输入中给出的顺序从 $$$1$$$ 到 $$$n$$$ 进行编号。如果有多个答案,请打印其中任何一个。

示例

输入 #1

3
4
2 1 10
3 1 3 5
5 5 4 3 2 1
3 10 20 30
3
4 1 2 3 4
4 2 3 4 5
4 3 4 5 6
2
3 1 3 5
3 4 3 2

输出 #1

2 3 
1 2 
-1