给定一个非循环有向图,由 $$$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