 # Undo Graph

After previous technical problems, Comisia decided to put an end to all hardware deficiencies. So far, n new servers have been acquired, some of them working on the same job. Comisia seeks the ability to control the way in which this distributed system works.

More concisely, the system should facilitate three types of operations:

• 1. Given servers x and y, assign the same job to them and to the network each of them resides in, respectively.
• 2. Undo the last x type 1 operations.
• 3. Output whether or not servers x and y are working on the same job.

## Input

The first line of input contains integers n and m - the number of servers and the number of applied operations, respectively.
The following m lines contain each of the operations, encoded using one of the formats:

• 1 x y - first type operation.
• 2 x - second type operation.
• 3 x y - third type operation.

Note: it is recommended that you parse the input, because of its large size. You can use the code provided below:

```#include <cstdio>

const int buffer=1<<13;
char buff[buffer]; int cnt=0;

//getInt() reads and returns one integer at a time
int getInt() {
int number = 0;
while(buff[cnt] < '0' || '9' < buff[cnt])
if(++cnt >= buffer) fread(buff, buffer, 1, stdin), cnt = 0;

while('0' <= buff[cnt] && buff[cnt] <= '9') {
number = number * 10 + buff[cnt] - '0';
if(++cnt >= buffer) fread(buff, buffer, 1, stdin), cnt = 0;
}

return number;
}

int main() {
int x = getInt();
printf("%d\n",x);
}
```

## Output

For each type 3 operation, you should output 1 if the given servers are working on the same job, and 0 on the contrary.

## Constraints

• 1 ≤ n, m ≤ 105
• The operations can always be performed.
• Self loops and multiple edges between a pair of nodes may exist.
• For type 1 and 3 operations, it is possible that x == y.
• None of the servers have any assigned job in the beginning.

InputOutput
10 11
1 1 5
1 2 6
1 5 2
3 1 2
2 1
3 1 2
3 1 5
3 2 6
1 1 2
2 2
3 2 6
1
0
1
1
0
Questions?