# 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;
}
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()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
{
int u, v;
scanf("%d%d", &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;
}```

0 条评论

• ### Planning mobile robot on Tree (EASY Version)（UVA12569，状态压缩)

题目链接：https://vjudge.net/problem/UVA-12569

• ### 搜索专题2 | 3D地宫寻路 POJ - 2251

上一篇我们做了一道棋子摆放的题目，采用的是DFS算法，本篇是一篇BFS算法，在刚开始学习搜索算法的时候，会觉得DFS和BFS算法非常相似，因为都是搜索然后得到结...

• ### 翻转瓷砖Fliptile（开关反转）- POJ 3279

Farmer John knows that an intellectually satisfied cow is a happy cow who will g...

• ### ZOJ 3326 An Awful Problem(模拟)

An Awful Problem ---- Time Limit: 1 Second      Memory Limit: 32768 KB ---- In o...

• ### Codeforce-Ozon Tech Challenge 2020-D. Kuroni and the Celebration（交互题+DFS)

After getting AC after 13 Time Limit Exceeded verdicts on a geometry problem, Ku...

• ### CF--思维练习--CodeForces - 216C - Hiring Staff （思维+模拟）

ACM思维题训练集合 A new Berland businessman Vitaly is going to open a household applia...

ASM是Java中比较流行的用来读写字节码的类库，用来基于字节码层面对代码进行分析和转换。

• ### CF--思维练习--CodeForces - 221C-H - Little Elephant and Problem （思维）

ACM思维题训练集合 The Little Elephant has got a problem — somebody has been touching h...