Closing the Farm

Interview

Time limit2sMemory limit512 MB

Summary

Barns close one by one in a given order, and the task asks after each step whether all open barns remain connected.

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

Problem

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

The farm has $N$ barns and $M$ bidirectional paths, each joining a pair of barns ( $1 \le N, M \le 200000$ ). To shut the farm down, John closes one barn at a time. When a barn closes, every path attached to it closes too and can no longer be used.

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

Input

The first line contains $N$ and $M$ . Each of the next $M$ lines contains the two barns joined by one path. Barns are numbered $1$ through $N$ . A path may join a barn to itself, and the same pair of barns may appear more than once. The last $N$ lines give the order in which the barns close, one barn per line, as a permutation of $1$ through $N$ .

Output

Print $N$ lines, each holding YES or NO. The first line tells whether the initial farm is fully connected, and line $i+1$ tells whether the farm is fully connected after $i$ barns have closed.

Examples3

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
```