Problem Description

There is a simple graph (not necessarily connected) consisting of $ N $ vertices and $ M $ undirected edges. The $ N $ vertices are numbered from $ 1 $ to $ N $ sequentially starting from vertex $ 1 $.

When three distinct vertices $ a, b, c $ are chosen such that there are edges connecting $ a $ to $ b $, $ b $ to $ c $, and $ c $ to $ a $, we say that $ (a, b, c) $ is a triplet.

We define an operation called "rotation" on a triplet $ (a, b, c) $ where:

• The new number for vertex $ a $ is the old number of vertex $ c $
• The new number for vertex $ b $ is the old number of vertex $ a $
• The new number for vertex $ c $ is the old number of vertex $ b $

We want to perform this rotation on any triplet any number of times so that the final numbers on the vertices are $ y_1, y_2, ..., y_N $ sequentially from vertex $ 1 $. Write a program to determine if such a transition is possible or not.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ : $ a_M $ $ b_M $ $ y_1 $ $ y_2 $ : $ y_N $

• The first line contains the number of vertices $N\ (1\ ≦\ N\ ≦\ 2000)$ and the number of edges $M\ (1\ ≦\ M\ ≦\ 2000)$ separated by a space.
• The next $ M $ lines contain different integers $ a_i $ and $b_i\ (1≦a_i,b_i≦N)$ separated by a space, representing that there is an edge between vertex $ a_i $ and vertex $ b_i $ in the graph.
• The next $ N $ lines contain different integers $y_1, y_2, ..., y_N\ (1≦y_i≦N)$ separated by a space, representing the target numbers for each vertex in the graph.

Output Format

Output $ "YES" $ if the transition described in the problem is possible, otherwise output $ "NO" $. End with a newline.

Sample Input and Output

Sample Input #1

3 3
1 2
2 3
3 1
2
3
1

Sample Output #1

YES

Sample Input #2

3 2
1 2
1 3
1
3
2

Sample Output #2

NO

Sample Input #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

Sample Output #3

NO

Notes/Hints

Sample Explanation 1

Since vertices $ (1, 2, 3) $ form a triplet, performing the rotation twice can achieve the target.

Sample Explanation 2

No triplets exist, so rotation is impossible, and the target numbering cannot be achieved.

Sample Explanation 3

No matter what operations are performed, it is impossible to change the number of vertex $ 6 $ to $ 1 $, so the target numbering cannot be achieved.

见题面 Input 部分

见题面 Output 部分