詹姆斯·邦德有一个抓捕敌人的新计划。有一些城市和它们之间的有向道路,使得可以使用这些道路在任何两个城市之间旅行。当敌人出现在某个城市时,邦德知道她的下一个目的地,但不知道她会选择哪条路去那里。
城市 $$$a$$$ 被称为有趣,如果对于每个城市 $$$b$$$,都存在从 $$$a$$$ 到 $$$b$$$ 的简单路径。通过一条简单的路径,我们可以理解一系列不同的城市,这样对于每两个相邻的城市,都存在一条从第一个城市到第二个城市的有向道路。
邦德的敌人是越狱情妇,所以只有在一个有趣的城市开始的追逐才有可能抓住她。詹姆斯想把他的人安排在这样的城市里。然而,如果没有足够的有趣城市,整个行动就没有意义,因为邦德的人可能会等待敌人太久。
你负责找到所有有趣的城市,或者说没有足够的城市。 James 所说的“不够”是指严格低于所有城市的 $$$20\%$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 2\,000$$$) — 测试用例的数量。每个测试用例描述如下:
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n \le 10^5$$$, $$$0 \leq m \le 2 \cdot 10^5$$$) - 它们之间的城市和道路的数量。以下$$$m$$$行中的每一行都包含两个整数$$$u$$$、$$$v$$$ ($$$u \neq v$$$; $$$1 \leq u, v \leq n$$$),表示从$$$u$$$到$$$v$$$有一条有向道路。
您可以假设在每对有序城市之间最多有一条道路。所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$,$$$m$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
如果严格小于 $$$20\%$$$ 的所有城市都是有趣的,则打印 $$$-1$$$。否则,令 $$$k$$$ 为感兴趣城市的数量。按升序打印 $$$k$$$ 不同的整数 - 有趣城市的索引。
示例
输入 #1
4 3 3 1 2 2 3 3 1 3 6 1 2 2 1 2 3 3 2 1 3 3 1 7 10 1 2 2 3 3 1 1 4 4 5 5 1 4 6 6 7 7 4 6 1 6 8 1 2 2 3 3 4 4 5 5 6 6 1 6 2 5 1
输出 #1
1 2 3 -1 1 2 3 5 -1
注意
在所有图画中,如果一个城市是绿色的,那么它很有趣;否则,它的颜色为红色。
在第一个样本中,每个城市都很有趣。
在第二个样本中,没有城市是有趣的。
在第三个样本中,城市 $$$1$$$、$$$2$$$、$$$3$$$ 和 $$$5$$$ 很有趣。
在最后一个样本中,只有城市 $$$1$$$ 是有趣的。它严格小于所有城市的$$$20\%$$$,所以答案是$$$-1$$$。