Graph? Are you sure?#233
If you can't believe, you can't achieve.
Initially, there are 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 and , which belong to the same component, as the shortest path from to . 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 queries of types:
1 \: u \: v \: c \: (1 \le c \le 4 \cdot 10^9) — add edge that connects vertexes and with value on it
2 \: u \: v \: — tell if the simple path between vertexes and is good. If there is no path between them, print
— tell the number of pairs of vertexes and (1 \leq a < b \leq n), such that they belong to the same component with and the path between them is considered good
— tell the number of pairs of vertexes and (1 \leq a < b \leq n), such that the path between them is considered good, and there exists a path from to .
It is guaranteed that in all queries of the first type, the edge connects two different components.
The first line of input contains two integers (1 \le n \le 2 \cdot 10^5) and (1 \le q \le 2 \cdot 10^5) — the number of vertices and queries accordingly.
Each of the following 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 integers , (1 \leq u \neq v \leq n), (1 \le c \le 4 \cdot 10^9)
t_i = 2\: defines a query of the second type and is followed by integers , (1 \le u,v \le n)
t_i = 3\: defines a query of the third type and is followed by integer (1 \le u \le n)
t_i = 4\: defines a query of the fourth type.
For each query of type print
-1, if there is no existing simple path
YES, if the simple path is considered good
NO otherwise.
For each query of types or print one integer — answer for corresponding query.
You have to answer queries in order they appear in the input.
Example 1
( points): for all t_i=1 u_i = 1;
( points): n,q \le 20;
( points): n,q \le 1000;
( points): t_i \le t_{i+1}, t_i \le 2, c = 1;
( points): t_i \le t_{i+1}, t_i \le 2, c \le 8;
( points): t_i \le t_{i+1}, t_i \le 2;
( points): q = n, t_i = 1 for 1 \le i < n, t_q = 4;
( points): there exists integer such that all t_i = 1 for all 1 \le i \le e, and for all e < j \le q t_i \neq 1;
( points): c \le 1000, graph and tests are generated randomly, i.e., for each vertex (2 \le v \le n) we randomly choose p_v (1 \le p_v < v), then we generate random permutation and make v = perm_v, p_v = perm_{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;
( points): no additional restrictions.