← 返回题目列表

Codeforces · 1036/G

G. 源和汇

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

给定一个非循环有向图,由 $$$n$$$ 个顶点和 $$$m$$$ 个边组成。该图不包含重边,也不存在自环。

如果该顶点没有传入边,则该顶点称为源。如果该顶点没有出边,则该顶点称为汇点。这些定义意味着某些顶点可以既是源点又是汇点。

给定图中的源数等于其中的汇数,并且每个数字不超过 $$$20$$$。

以下算法应用于该图:

1. 如果图没有源和汇则退出;
2. 选择任意源 $$$s$$$、任意接收器 $$$t$$$,向图中添加一条从 $$$t$$$ 到 $$$s$$$ 的边,然后转到步骤 $$$1$$$(该操作将 $$$s$$$ 从源中弹出,将 $$$t$$$ 从接收器中弹出)。注意$$$s$$$和$$$t$$$可能是同一个顶点,那么就添加了一个自循环。

最后检查图是否变得强连接(即任何顶点都可以从任何其他顶点到达)。

您的任务是检查图是否变为强连接,无论算法第二步选择源和汇。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 10^6$$$) — 分别是图中的顶点数和边数。

接下来的 $$$m$$$ 行包含两个整数 $$$v_i, u_i$$$ ($$$1 \le v_i, u_i \le n$$$, $$$v_i \ne u_i$$$) — 原始图的第 $$$i$$$ 条边的描述。

保证图中的源数和汇数相同,且不超过$$$20$$$。保证给定的图不包含重边。保证图中不包含环。

输出

如果无论算法第二步中源和汇的选择如何,图形都变为强连接,则打印“YES”。否则打印“NO”。

示例

输入 #1

3 1
1 2

输出 #1

NO

输入 #2

3 3
1 2
1 3
2 3

输出 #2

YES

输入 #3

4 4
1 2
1 3
4 2
4 3

输出 #3

YES