← 返回题目列表

AtCoder · code_festival_exhibition_a

A. 谜题

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

問題文

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 并且无法实现所需的编号。