CF915D.Almost Acyclic Graph

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

You are given a directed graph consisting of $n$ vertices and $m$ edges (each edge is directed, so it can be traversed in only one direction). You are allowed to remove at most one edge from it.

Can you make this graph acyclic by removing at most one edge from it? A directed graph is called acyclic iff it doesn't contain any cycle (a non-empty path that starts and ends in the same vertex).

输入格式

The first line contains two integers $n$ and $m$ ( $2<=n<=500$ , $1<=m<=min(n(n-1),100000)$ ) — the number of vertices and the number of edges, respectively.

Then $m$ lines follow. Each line contains two integers $u$ and $v$ denoting a directed edge going from vertex $u$ to vertex $v$ ( $1<=u,v<=n$ , $u≠v$ ). Each ordered pair $(u,v)$ is listed at most once (there is at most one directed edge from $u$ to $v$ ).

输出格式

If it is possible to make this graph acyclic by removing at most one edge, print YES. Otherwise, print NO.

输入输出样例

输入#1
```
3 4
1 2
2 3
3 2
3 1
```
输出#1
```
YES
```
输入#2
```
5 6
1 2
2 3
3 2
3 1
2 1
4 5
```
输出#2
```
NO
```

说明/提示

In the first example you can remove edge , and the graph becomes acyclic.

In the second example you have to remove at least two edges (for example, and ) in order to make the graph acyclic.

首页