A - パズル 解説 /

実行時間制限: 1 sec / メモリ制限: 256 MB

問題文

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 にすることは不可能であり，目標の番号付けは達成できない．