## CCO '24 P6 - Telephone Plans

View as PDF

Points: 30 (partial)
Time limit: 4.0s
Memory limit: 1G

Problem types

The "Dormi's Fone Service" is now the only telephone service provider in CCOland. There are houses in CCOland, numbered from to . 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 queries of the following forms:

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

Also, some test cases may be encrypted. For the test cases that are encrypted, the arguments , , or 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).

#### Input Specification

The first line of input will contain . denotes that the input is not encrypted, while denotes that the input is encrypted.

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

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

For the -th query , it is guaranteed that (after decrypting if ) for type 1 and 2 queries and for type 3 queries.

Marks Awarded Bounds on Bounds on Encrypted?
3 marks
2 marks
4 marks
2 marks
4 marks
5 marks
5 marks

#### Output Specification

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

#### Sample Input 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

#### Sample Output 1

0
1
3
3
1
3
3
5

#### Explanation of Output for Sample Input 1

This test case is not encrypted.

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

For the query, only houses and could have called each other.

For the query, is the set of pairs that could have called each other.

The query is the same.

For the query, only houses and could have called each other.

For the query, there is a point in time where could have called each other.

For the query, the set of pairs that could have called each other is .

For the query, the set of pairs that could have called each other at any previous time is .

#### Explanation of Output for Sample Input 2

Encrypted version of sample 1.

#### Sample Input 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

#### Sample Output 2

0
1
3
3
1
3
3
5