Graph? Are you sure?

Initially, there are $n$ vertexes and no edges. Each of the added edges has an integer $c_i$ written on it. We define a simple path between two vertexes $a$ and $b$, which belong to the same component, as the shortest path from $a$ to $b$. Consider a simple path between two vertexes being good if each value on this path has the even number of entries. You have to answer $q$ queries of $4$ types:

• $1uvc$ ($1\le c\le 4\cdot 10^9$) — add edge that connects vertexes $u$ and $v$ with value $c$ on it

• $2uv$ — tell if the simple path between vertexes $u$ and $v$ is good. If there is no path between them, print $-1$

• $3u$ — tell the number of pairs of vertexes $a$ and $b$ ($1\le a<b\le n$), such that they belong to the same component with $u$ and the path between them is considered good

• $4$ — tell the number of pairs of vertexes $a$ and $b$ ($1\le a<b\le n$), such that the path between them is considered good, and there exists a path from $a$ to $b$.

It is guaranteed that in all queries of the first type, the edge connects two different components.

Input

The first line of input contains two integers $n$ ($1\le n\le 2\cdot 10^5$) and $q$ ($1\le q\le 2\cdot 10^5$) — the number of vertices and queries accordingly.

Each of the following $q$ lines contain a description of the query. First integer $t_i$ defines the type of the query.

• $t_i=1$ defines a query of the first type and is followed by $3$ integers $u$, $v$ ($1\le u\ne v\le n$), $c$ ($1\le c\le 4\cdot 10^9$)

• $t_i=2$ defines a query of the second type and is followed by $2$ integers $u$, $v$ ($1\le u,v\le n$)

• $t_i=3$ defines a query of the third type and is followed by $1$ integer $u$ ($1\le u\le n$)

• $t_i=4$ defines a query of the fourth type.

Output

For each query of type $2$ print

• -1, if there is no existing simple path

• YES, if the simple path is considered good

• NO otherwise.

For each query of types $3$ or $4$ print one integer — answer for corresponding query.

You have to answer queries in order they appear in the input.

Examples

Scoring

1. ($5$ points): for all $t_i=1$ $u_i=1$;

2. ($5$ points): $n,q\le 20$;

3. ($7$ points): $n,q\le 1000$;

4. ($3$ points): $t_i\le t_{i+1}$, $t_i\le 2$, $c=1$;

5. ($6$ points): $t_i\le t_{i+1}$, $t_i\le 2$, $c\le 8$;

6. ($11$ points): $t_i\le t_{i+1}$, $t_i\le 2$;

7. ($9$ points): $q=n$, $t_i=1$ for $1\le i<n$, $t_q=4$;

8. ($17$ points): there exists integer $e$ such that all $t_i=1$ for all $1\le i\le e$, and for all $e<j\le q$ $t_i\ne 1$;

9. ($9$ points): $c\le 1000$, graph and tests are generated randomly, i.e., for each vertex $v$ ($2\le v\le n$) we randomly choose $p_v$ ($1\le p_v<v$), then we generate random permutation $perm$ and make $v=per{m}_v$, $p_v=per{m}_{p_v}$. Type of query is chosen randomly (we won't choose first type if there are no edges to add). All values in queries are picked randomly;

10. ($28$ points): no additional restrictions.