시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 1024 MB4000.000%

문제

The “Dormi’s Fone Service” is now the only telephone service provider in CCOland. There are $N$ houses in CCOland, numbered from $1$ to $N$. Each telephone line connects two distinct houses such that all the telephone lines that ever exist form a forest.

There is an issue where the phone lines are faulty, and each phone line only exists for a single interval of time. Two houses can call each other at a certain time if there is a path of phone lines that starts at one of the houses and ends in the other house at that time.

We would like to process $Q$ queries of the following forms:

  • $1$ $x$ $y$: Add a phone line between houses $x$ and $y$. It is guaranteed that a phone line between houses $x$ and $y$ was never added before.
  • $2$ $x$ $y$: Remove the phone line between houses $x$ and $y$. It is guaranteed that a phone line currently exists between houses $x$ and $y$.
  • $3$ $t$: Compute the number of pairs of different houses that can call each other at some time between the current query and $t$ queries ago. To be more clear, let $G_q$ be the state of CCOland after the $q$-th query, where $G_0$ is the state of CCOland before any queries. If this is the $s$-th query, then count the number of pairs of houses that are connected in at least one of $G_{s-t} , G_{s-t+1}, \dots , G_s$.

Also, some test cases may be encrypted. For the test cases that are encrypted, the arguments $x$, $y$, or $t$ are given as the bitwise xor of the true argument and the answer to the last query of type $3$ (if there have been no queries of type $3$, then the arguments are unchanged).

입력

The first line of input will contain $E$ ($E \in \{0, 1\}$). $E = 0$ denotes that the input is not encrypted, while $E = 1$ denotes that the input is encrypted.

The second line contains two space-separated integers $N$ and $Q$, representing the number of houses in CCOland and the number of queries, respectively.

The next $Q$ lines contain queries as specified above (queries are encrypted or not depending on $E$).

For the $q$-th query ($1 ≤ q ≤ N$), it is guaranteed that (after decrypting if $E = 1$) $1 ≤ x, y ≤ N$ for type $1$ and $2$ queries and $0 ≤ t ≤ q$ for type $3$ queries.

출력

For each query of type $3$, output the answer to the query on a new line.

서브태스크

Subtask Score Bounds on $N$ Bounds on $Q$ Additional constraints
1 3 $1 ≤ N ≤ 30$ $1 ≤ Q ≤ 150$ $E = 0$
2 2 $1 ≤ N ≤ 30$ $1 ≤ Q ≤ 150$ $E = 1$
3 4 $1 ≤ N ≤ 2\, 000$ $1 ≤ Q ≤ 6\, 000$ $E = 0$
4 2 $1 ≤ N ≤ 2\, 000$ $1 ≤ Q ≤ 6\, 000$ $E = 1$
5 4 $1 ≤ N ≤ 100\, 000$ $1 ≤ Q ≤ 300\, 000$ $E = 0$
6 5 $1 ≤ N ≤ 100\, 000$ $1 ≤ Q ≤ 300\, 000$ $E = 1$
7 5 $1 ≤ N ≤ 500\, 000$ $1 ≤ Q ≤ 1\, 500\, 000$ $E = 1$

예제 입력 1

0
4 12
3 0
1 1 2
3 0
1 1 3
3 0
3 5
2 2 1
3 0
3 8
1 1 4
3 0
3 11

예제 출력 1

0
1
3
3
1
3
3
5

This test case is not encrypted.

For the $1$st query, no pairs of different houses could have called each other.

For the $3$rd query, only houses $1$ and $2$ could have called each other.

For the $5$th query, $\{(1, 2),(1, 3),(2, 3)\}$ is the set of pairs that could have called each other. The $6$th query is the same.

For the $8$th query, only houses $1$ and $3$ could have called each other.

For the $9$th query, there is a point in time where $\{(1, 2),(1, 3),(2, 3)\}$ could have called each other.

For the $11$th query, the set of pairs that could have called each other is $\{(1, 3),(1, 4),(3, 4)\}$.

For the $12$th query, the set of pairs that could have called each other at any previous time is $\{(1, 2),(1, 3),(1, 4),(2, 3),(3, 4)\}$.

예제 입력 2

1
4 12
3 0
1 1 2
3 0
1 0 2
3 1
3 6
2 1 2
3 3
3 9
1 2 7
3 3
3 8

예제 출력 2

0
1
3
3
1
3
3
5

Encrypted version of sample 1.

채점 및 기타 정보

  • 예제는 채점하지 않는다.