| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 1024 MB | 4 | 0 | 0 | 0.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:
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$ |
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
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)\}$.
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
0 1 3 3 1 3 3 5
Encrypted version of sample 1.