CodeForces 982F：The Meeting Place Cannot Be Changed（有向图）

题目：

Petr is a detective in Braginsk. Somebody stole a huge amount of money from a bank and Petr is to catch him. Somebody told Petr that some luxurious car moves along the roads without stopping.

Petr是Braginsk镇的一名侦探，现在有个人偷了很多钱，Petr需要抓捕他。有人告诉Petr有一些豪华车在路上违法行驶。

Petr knows that it is the robbers who drive the car. The roads in Braginsk are one-directional and each of them connects two intersections. Petr wants to select one intersection such that if the robbers continue to drive the roads indefinitely, they will sooner or later come to that intersection. The initial position of the robbers is unknown. Find such an intersection that fits the requirements.

Petr知道这是那些小偷在开车。Braginsk镇的路是单向的，并且每一条路有2个交点，Petr想选一个交点，如果小偷一直开车，他迟早会来到那个交点。小偷初始位置并不清楚，让你帮忙寻找这个交点。

Input

The first line of the input contains two integers n and m (2≤n≤10^5,2≤m≤5⋅10^5) — the number of intersections and the number of directed roads in Braginsk, respectively.

Each of the next mm lines contains two integers uiui and vivi (1≤ui,vi≤n,ui≠vi) —

the start and finish of the i-th directed road. It is guaranteed that the robbers can move along the roads indefinitely.

Output

Print a single integer kk — the intersection Petr needs to choose. If there are multiple answers, print any. If there are no such intersections, print −1−1.

Examples

input

Copy

5 6

1 2

2 3

3 1

3 4

4 5

5 3

output

Copy

3

input

Copy

3 3

1 2

2 3

3 1

output

Copy

1

Note

In the first example the robbers can move, for example, along the following routes: (1−2−3−1)(1−2−3−1), (3−4−5−3)(3−4−5−3), (1−2−3−4−5−3−1)(1−2−3−4−5−3−1). We can show that if Petr chooses the 33-rd intersection, he will eventually meet the robbers independently of their route.

题意： 劫匪的初始位置未知，他沿着道路不停的移动， 城市的道路是单向的，并且每条道路都连接两个交叉路口， 选择一个交叉路口，如果劫匪继续无限期地开车， 他们迟早会到达那个交叉路口。 分析：

考察有向图的存储、遍历、判断有环 先按入度从大到小给每个点排序，然后枚举每个点当作答案，判断当前点是否行

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 50; //数据量
int n, m; //节点数、边数
int head[N], to[N], nxt[N], tot; //存储有向图
inline void add(int x, int y) //x为起点，y为终点建边
{
    to[tot] = y;
    nxt[tot] = head[x];
    head[x] = tot++;
}
int vis[N];//标记已经访问过的节点
int in[N], id[N];
bool dt[N], k;
const bool cmp(int a, int b) //间接排序函数
{
    return in[a] < in[b]; //按入度排序
}
//计算搜索时间
inline double FIND_TIME()
{return clock() / (double)CLOCKS_PER_SEC;}
void dfs(int x)
{
    vis[x] = 1; //标记节点已经访问过
    for (int i = head[x]; ~i; i = nxt[i])
    {
        if (!vis[to[i]]) //下一个节点没有访问过
            dfs(to[i]);
        if (vis[to[i]] == 1) //下一个节点访问过
            k = 1;
        if (k)   return ;
    }
    vis[x] = 2; //DFS回溯
}
inline bool check(int x)//检查每一个点
{
    memset(vis, 0, sizeof(vis));
    vis[x] = 2;
    k = 0;
    for (int i = 1; i <= n; i++)
        if (!vis[i]) {
            dfs(i);
            if (k) {
                for (int i = 1; i <= n; i++)
                    if (vis[i] != 1)
                        dt[i] = 1;
                return false;
            }
        }
    return true;
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v); //建边
        ++in[u];//更新度
    }
    for (int i = 1; i <= n; i++)
        id[i] = i; //节点编号
    sort(id + 1, id + 1 + n, cmp); //排序
    for (int i = 1; i <= n; i++) {
        if (FIND_TIME() > 0.9) break; //时间限制为1s
        if (!dt[id[i]] && check(id[i])) //此点合法
        {
            printf("%d\n", id[i]); //输出路口的编号
            return 0;
        }
    }
    puts("-1");//不存在这样的点
    return 0;
}