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.
Sample
| Input | Output |
|---|---|
| 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 |
First of all, let's take a look at the 3 types of operations defined in the statement. The first operation adds and edge in the (multi)graph, the second type reverts type one operations and the third one asks whether or not two nodes are in the same connected component.
Trying to build a suitable algorithm from scratch looks tricky, so we will begin by making some observations.
Firstly, we can analyse a simpler problem, the one in which we don't have any undo operations. This would be solved using a Disjoint-set data structure. Adding an edge is equivalent to merging two disjoint sets and answering a question reduces to verifying whether or not two nodes are in the same set.
Now let's get back to the original problem. Suppose we're dealing with a small number of undo operations. In this case, it would be enough to store the entire input, and then mantain a back-up disjoint-set structure before the update. Of course, that would solve any undo operation in linear time. However, the key observation is that not all elements necessarily have to be updated (e.g. when there is just one unde operation, instead of changing just a few values, you update the whole data structure).
To enhance the performance we have to observe that a type one operation modifies O(log* N) values (on average) from the disjoint data set. This means that going one step backwards also modifies O(log* N) values. When we update we can just retain in a stack the values that we have changed. When we want to go backwards, we restore the old values mantained in the disjoint data sets. This brings our final time complexity to O(M log *N) as one operation can be done once and reversed only once, implying a constant factor of 2.
