問題文
N 一个顶点和 M 由本书的无向边组成的单纯图(不一定是连通的)。 N 一个顶点有,顶点 1 按顺序排列,1,2,...,N 并编号。
某些不同的 3 个顶点 a,b,c 被选中时,a 和 b 所连接的边, b 和 c 所连接的边,以及 c 和 a 所连接的边存在时, (a,b,c) 为 3 个组被称为一个组。
那么,3 个已组成组的顶点 (a,b,c) 被选中,
- 頂点 a 是顶点 c 旧号码 定义一个名为“旋转”的操作,重写顶点上写入的数字,使其变为
- 頂点 b 是顶点 a 旧号码 定义一个名为“旋转”的操作,重写顶点上写入的数字,使其变为
- 頂点 c 是顶点 b 旧号码 定义一个名为“旋转”的操作,重写顶点上写入的数字,使其变为
。
将此轮换更改为任意 3 对集合重复此操作任意次,最后每个顶点上写的数字就是该顶点。 从 1 开始 我希望它是 y_1,y_2,...,y_N 。 编写一个程序来确定这种转换是否可能。
入力
输入是按以下格式从标准输入给出的。
N M a_1 b_1 a_2 b_2 : a_M b_M y_1 y_2 : y_N
- 1 行显示图中的顶点数。 N (1 ≦ N ≦ 2000) 和边数 M (1 ≦ M ≦ 2000) 之间用空格分隔。
- 2 在 M 行,不同的整数代表每一侧的信息 a_i 和 b_i (1≦a_i,b_i≦N) 用空格分隔。这是图中的顶点 a_i 和顶点 表示 b_i 已连接的信息。
- 1+M 在 N 行,一个不同的整数,表示目标图每个顶点写入的数字 y_1,y_2,...,y_N (1≦y_i≦N) 之间用空格分隔。
出力
如果问题陈述中给出的转换是可能的 "YES" ,如果不可能 输出 "NO" 。在末尾添加换行符。
入力例1
3 3 1 2 2 3 3 1 2 3 1
出力例1
YES
頂点 (1,2,3) 被给予 3 由于是双套,所以轮换为 您可以通过执行 2 次来实现您的目标。
入力例2
3 2 1 2 1 3 1 3 2
出力例2
NO
3 两组 由于不存在 1 ,因此无法进行旋转并且无法实现所需的编号。
入力例3
8 11 1 2 1 3 2 3 2 4 2 5 3 6 4 5 5 6 6 7 6 8 7 8 6 2 3 4 5 1 7 8
出力例3
NO
无论你做什么操作,顶点 6 号码 1 并且无法实现所需的编号。