← 返回题目列表

Codeforces · 1572/A

A. 书

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

给你一本包含 $$$n$$$ 章节的书。

每章都有一个指定的其他章节列表,需要理解这些章节才能理解本章。要理解一章,您必须在理解其所需列表中的每一章之后再阅读该章。

目前您不理解任何章节。你将从头到尾反复阅读这本书,直到理解整本书。注意,如果你在读某一章的时候,有些必读章节不理解,那么你就没有理解这一章。

确定你需要读多少遍书才能理解每一章,或者确定无论你读多少遍书你都永远无法理解每一章。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 2\cdot10^4$$$)。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$) — 章节数。

然后是 $$$n$$$ 行。第 $$$i$$$ 行以整数 $$$k_i$$$ 开头 ($$$0 \le k_i \le n-1$$$) — 理解第 $$$i$$$ 章节所需的章节数。然后 $$$k_i$$$ 整数 $$$a_{i,1}, a_{i,2}, \dots, a_{i, k_i}$$$ ($$$1 \le a_{i, j} \le n, a_{i, j} \ne i, a_{i, j} \ne a_{i, l}$$$ for $$$j \ne l$$$) 接下来是理解$$$i$$$第$$$章。

保证所有测试用例的 $$$n$$$ 和 $$$k_i$$$ 之和不超过 $$$2\cdot10^5$$$。

输出

对于每个测试用例,如果可以理解整本书,则打印您将阅读它的次数,否则打印 $$$-1$$$。

示例

输入 #1

5
4
1 2
0
2 1 4
1 2
5
1 5
1 1
1 2
1 3
1 4
5
0
0
2 1 2
1 2
2 2 1
4
2 2 3
0
0
2 3 2
5
1 2
1 3
1 4
1 5
0

输出 #1

2
-1
1
2
5

注意

在第一个例子中,我们将在第一次阅读中理解章节$$$\{2, 4\}$$$,在第二次阅读中理解章节$$$\{1, 3\}$$$。

在第二个例子中,每一章都需要理解其他一些章节,因此不可能理解这本书。

在第三个例子中,每一章只需要书中前面出现的章节,因此我们可以一次性理解所有内容。

在第四个例子中,我们将在第一读中理解章节$$$\{2, 3, 4\}$$$,在第二读中理解章节$$$1$$$。

在第五个例子中,我们将理解从 $$$5$$$ 到 $$$1$$$ 的每次阅读中的一章。