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 each 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 number of nodes in the graph and the number of edges that Andy is trying to add, respectively.

The following ~e~ lines each contain two integers ~a~ and ~b~, stating that 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 a forest after adding that edge.

Constraints

• ~1 \le n, e \le 5 \times 10^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