Andy wants to construct an undirected graph with no cycles, except, he doesn't know how. Instead, he tries to randomly add edges between two nodes. Tell Andy whether adding the edge will result in a forest (an undirected graph with no cycles). If so, add the edge to the graph.

The graph begins with no edges.

Input

The first line contains integers ~n~ and ~e~, the numbers of nodes in the graph, and the number of edges that Andy is trying to add, respectively.

The following ~e~ lines contains a b, stating Andy wishes to add an undirected edge between a and b.

Output

For each edge Andy tries to add, output a line containing Yes or No, answering whether the graph will remain as a forest.

Constraints

• ~1 \le n,e \le 5\times10^5~
• ~1 \le a,b \le n~

Example 1

Input

5 10
3 3
1 1
2 4
3 3
4 4
5 4
3 5
4 3
1 3
2 5

Output

No
No
Yes
No
No
Yes
Yes
No
Yes
No

Example 2

Input

10 20
9 4
3 4
10 4
4 3
9 4
10 3
10 5
5 3
9 10
6 10
6 10
3 4
4 8
7 9
1 2
8 2
3 6
10 6
8 4
5 9

Output

Yes
Yes
Yes
No
No
No
Yes
No
No
Yes
No
No
Yes
Yes
Yes
Yes
No
No
No
No