In the ancient times of OI, there was a story:

One day, little W went to play in the forest. Upon returning, he told little V, "I found many trees that can move!" Little V replied, "What's so strange about that? I can maintain the structure of any tree with my fingers."

A few days later, little W went to play in the desert. Upon returning, he told little V, "I found many cacti that can move!" Little V replied, "What's so strange about that? I can maintain the structure of any cactus with my toes."

Little S saw this story and was deeply moved. He decided to start step by step, starting with cacti, and starting with stationary cacti.

In this problem, we define:

If an undirected connected graph has the property that every edge belongs to at most one simple cycle, and there are no self-loops, we call it a cactus.

The definitions of the shortest path (which must be a simple path) and the longest simple path between two points in a cactus are the same as in a general undirected graph.

In this problem, we also guarantee that the length of every simple cycle is odd. This implies that there are no multiple edges, and the shortest path and the longest simple path between any two points are unique.

To prove that you can indeed maintain a cactus, we give you $n$ nodes, labeled from $1$ to $n$, where node $1$ is the root of the cactus. It has $m$ edges, where the $i$-th edge connects nodes $u_i$ and $v_i$.

Each node has a color (black or white), initially all black. There are $q$ operations, each in the format $op$ $x$ ($1 \leq op \leq 3, 1 \leq x \leq n$):

• If $op=1$, toggle the state of all nodes on the shortest path from node $x$ to the root (black becomes white, white becomes black);
• If $op=2$, toggle the state of all nodes on the longest simple path from node $x$ to the root;
• If $op=3$, query the number of black nodes in the sub-cactus of node $x$. The sub-cactus of node $x$ is defined as: the connected component containing $x$ after removing all edges on all simple paths from the root to node $x$.

Input

The first line contains three space-separated positive integers $n, m, q$, representing $n$ nodes, $m$ edges, and $q$ operations.

The next $m$ lines each contain two space-separated positive integers $u_i, v_i$, representing an edge.

The next $q$ lines each represent an operation, in the format described above.

Output

For each operation with $op=3$, output the result on a single line.

Examples

Input 1

7 9 11
1 2
1 3
2 3
3 4
3 5
4 5
5 6
5 7
6 7
3 1
3 2
3 3
1 7
3 1
3 2
3 3
2 7
3 1
3 2
3 3

Output 1

7
1
5
3
1
2
4
0
3

Input 2

See sample data download. This data satisfies the constraints and conventions of Subtask 4.

Input 3

See sample data download. This data satisfies the constraints and conventions of Subtask 5.

Input 4

See sample data download. This data satisfies the constraints and conventions of Subtask 6.

Subtasks

This problem uses bundled testing. Each subtask contains several test cases, divided into 8 subtasks. You only receive points for a subtask if you pass all test cases within that subtask.

Constraints for the first seven subtasks

Time limit: $1\texttt{s}$.

Memory limit: $768\texttt{MB}$.

$n, q \leq 50000$.

Subtask 1 (7 points)

$n \leq 2, q \leq 2000$.

Subtask 2 (14 points)

$n \leq 20, q \leq 2000$.

Subtask 3 (9 points)

$n, q \leq 2000$.

Subtask 4 (17 points)

Guaranteed $m=n-1$, $u_i=i, v_i=i+1$, and no operations with $op=2$.

Subtask 5 (14 points)

Guaranteed $m=n-1$, $u_i < v_i$, and no operations with $op=2$.

Subtask 6 (11 points)

Guaranteed no operations with $op=2$.

Subtask 7 (18 points)

No special constraints or conventions.

Subtask 8 (10 points)

Memory limit reduced to $128\texttt{MB}$.