当前没有测试数据。

题目描述

You are given an undirected graph with $\ N$ vertices and $\ M$ edges. The edges are numbered from $\ 1$ to $\ M$ . Denote the set $\ S(x)$ as: All the vertices we can reach from vertex $\ x$ by exactly one edge.

You are supposed to deal with $\ Q$ operations of the following two types: $\ (1,l,r)$-- reverse the status of edges numbered between $\ l$ to $\ r$ $(1 \leq l \leq r \leq M)$ . i.e. Delete the edge if it is in the graph, otherwise add it to the graph. $\ (2,u,v)$ -- ask whether $\ S(u)$ and $\ S(v)$ are exactly the same $(1 \leq u \leq v \leq N)$.

Note that all the $\ M$ edges are in the graph at the beginning.

输入格式

The input contains multiple cases. The first line of the input contains a single positive integer $\ T$ , the number of cases.

For each case, the first line contains two integers $N\ (1 \leq N \leq 100000)$ and $M\ (1 \leq M \leq 200000)$, the number of vertices and edges in the graph. In the following $\ M$ lines, the $\ i$-th line contains two integers $\ (1 \le u_i,v_i \le N)$ , describing the the $\ i$-th edge $(u_i,v_i)$ . Each edge appears in the input at most once. The $\ (M+2)$-th line contains a integer $Q\ (1 \leq Q \leq 200000)$, the number of operations. In the following $\ Q$ lines, each line contains three integers, describing an operation.

The total sum of $\ N$ over all cases does not exceed $\ 150000$. The total sum of $M\$ over all cases does not exceed $\ 800000$. The total sum of $\ Q$ over all cases does not exceed $\ 600000$.

输出格式

For each case, print a string in a line. The length of the string should equal the number of operations of type $\ 2$. If the answer is yes, the $\ i$-th character of the string should be '1', otherwise it should be '0'. Check the samples for more details.

样例

样例输入 1

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

样例输出 1

10