给定一个由 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$$)才能使图成为非循环图。