Closing the Farm

Interview

Time limit2sMemory limit512 MB

Summary

After each barn closure in the given order, report whether the remaining open barns stay connected by open paths.

Level: Medium6 of 10
Topics: Union-find, Graph
Solved: No attempts yet

Problem

Farmer John and his cows are leaving for a long vacation, so John wants to close the farm for a while and save money.

The farm has $N$ barns and $M$ two-way paths, and each path joins a pair of barns ( $1 \le N, M \le 3000$ ). John closes the farm one barn at a time. When a barn closes, every path touching that barn closes with it and can no longer be used.

John wants to know, at the start and after each closing, whether the farm is fully connected. The farm is fully connected when you can travel from any open barn to any other open barn along a series of open paths. The farm is in poor repair, so it may not be fully connected even at the start. A farm with only one open barn counts as fully connected.

Input

The first line contains $N$ and $M$ . Each of the next $M$ lines contains the numbers of the two barns that one path joins. Barns are numbered $1$ through $N$ . More than one path may join the same pair of barns. The last $N$ lines give a permutation of $1$ through $N$ , the order in which the barns close.

Output

Print $N$ lines, each holding YES or NO. The first line tells whether the farm is fully connected at the start, and line $i+1$ tells whether the farm is fully connected after the $i$ th closing.

Examples4

Example 1
Input
```
4 3
1 2
2 3
3 4
3
4
1
2
```
Expected output
```
YES
NO
YES
YES
```
Example 2
Input
```
2 1
1 2
1
2
```
Expected output
```
YES
YES
```
Example 3
Input
```
4 2
1 2
3 4
1
2
3
4
```
Expected output
```
NO
NO
YES
YES
```

Example 4

Input

Expected output

YES
NO
NO
NO
YES