← 返回题目列表

Codeforces · 915/D

D. 几乎无环图

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

给定一个由 n 个顶点和 m 个边组成的有向图(每条边都是有向的,因此只能在一个方向上遍历)。您最多可以删除其中的一条边。

你能通过删除最多一条边来使该图成为非循环图吗?有向图称为非循环图,当且仅当它不包含任何循环(在同一顶点开始和结束的非空路径)。

输入

第一行包含两个整数 n 和 m (2 ≤ n ≤ 500, 1 ≤ m ≤ min(n(n - 1), 100000)) — 分别是顶点数和边数。

接下来是 m 行。每行包含两个整数 u 和 v,表示从顶点 u 到顶点 v 的有向边(1 ≤ u,v ≤ n,u ≠ v)。每个有序对 (u, v) 最多列出一次(从 u 到 v 最多有一条有向边)。

输出

如果可以通过删除至多一条边来使该图成为非循环图,则打印 YES。否则,打印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

注意

在第一个示例中,您可以删除边 $$2\rightarrow3$$,并且图形变为非循环。

在第二个示例中,您必须删除至少两条边(例如,$$2 \rightarrow 1$$ 和 $$2\rightarrow3$$)才能使图成为非循环图。