← 返回题目列表

Codeforces · 982/F

F. 集合地点无法更改

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

Petr 是布拉金斯克的一名侦探。有人从银行偷了一大笔钱,彼得要去抓他。有人告诉彼得,有一辆豪华轿车在路上不停地行驶。

Petr 知道开车的是强盗。布拉金斯克的道路是单向的,每条道路连接两个十字路口。 Petr 希望选择一个十字路口,这样如果劫匪继续无限期地在道路上行驶,他们迟早会来到该十字路口。劫匪最初的位置未知。找到这样一个符合要求的交点。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n \le 10^5$$$, $$$2 \leq m \leq 5 \cdot 10^5$$$) — 分别是布拉金斯克的交叉口数量和有向道路数量。

接下来的 $$$m$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$) - 第 $$$i$$$ 有向道路的起点和终点。保证了强盗可以无限期地沿着道路移动。

输出

打印单个整数 $$$k$$$ — Petr 需要选择的交集。如果有多个答案,请打印其中一个。如果没有这样的交集,则打印 $$$-1$$$。

示例

输入 #1

5 6
1 2
2 3
3 1
3 4
4 5
5 3

输出 #1

3

输入 #2

3 3
1 2
2 3
3 1

输出 #2

1

注意

在第一个示例中,强盗可以沿着以下路线移动:$$$(1-2-3-1)$$$、$$$(3-4-5-3)$$$、$$$(1-2-3-4-5-3-1)$$$。我们可以证明,如果 Petr 选择 $$$3$$$-rd 路口,他最终会遇到强盗,无论他们的路线如何。