Almost Acyclic Graph

题意翻译

给定一个 $n$ 个顶点，$m$ 条边的有向图。你允许从其中去掉最多一条边。 你能够去掉最多一条边就让这个图无环吗？我们称一个有向图无环，当且仅当它不包含一个环(起点和终点相同的路径)。 #### 输入格式： 第一行两个正整数 $n,m$（$2\le n\le 500,1\le m\le min(n(n-1),10^5)）$，代表图的顶点数和边数。 接下来 $m$ 行，每行两个数 $u,v$，表示有一条从 $u$ 到 $v$ 的有向边（$1\le u,v\le n,u\ne v$）。一对 $(u,v)$ 最多出现一次。 #### 样例说明： 第一个样例中，去掉 $2\to 3$ 的边即可。 第二个样例中，需要至少去掉两条边（例如 $2\to 1$ 和 $2\to 3$）才能让这个图变成无环图。 Translated by @小粉兔

题目描述

You are given a [directed graph](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Directed_acyclic_graph) 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.