Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Team Forming

By shefin · Limits 1s, 512 MB

Ben is the instructor of a camp. He is forming several teams consisting of the students of the camp. But the weird thing is there are no rules for forming the teams. Whenever two students want to be in a team, Ben assigns both of them and the members of their teams in a single team. Ben calls this operation as assignment operation. As this operation is performed without any kind of checking, sometimes the size of a team becomes very large. Here, the size of a team means the number of members in that team.
Ben is a lazy person. He doesn't always check the size of the teams. But when he checks, he follows these procedures:

  1. He chooses a student u and a special number x.

  2. If the size of the student u's current team is already less than x, he skips the further procedures. Else, he finds out the first valid assignment operation (valid assignment operations are those which haven't been canceled out yet) in which the size of the student u's team becomes greater or equal to x. Let's denote this valid assignment operation as special operation.

  3. Ben then reforms the teams as they were just after executing this special operation and cancels out all the assignment operations which have been executed after the special operation till now. Once an assignment operation is canceled out, it is never considered as a valid assignment operation & will always be ignored in further operations as if they never existed.

Ben is feeling that the whole thing is complex for him to manage. So, he needs your help.

Input

The first line of the input contains an integer T (1 ≤ T ≤ 10), the number of the test cases.

In each of the cases, the first line contains two integers N (2 ≤ N ≤ 105) and Q (1 ≤ Q ≤ 105), the number of the students and the number of the queries. Then there will be Q lines denoting the queries. The queries will be of 3 types:

Type 1: 1 u v — assign the students u, v (1 ≤ u, v ≤ N, (u ≠ v)) and the members of their teams in a single team.

Type 2: 2 u — print the size of the team student u is currently a member of.

Type 3: 3 u x — perform the checking operation as described in the problem statement and print the size of the current team of student u. (2 ≤ x ≤ N).

Output

In each case, print "Case y:" (without quotes) in a single line first, where y is the case number.
After that for each of the type 2 and type 3 queries, print the corresponding output in a single line.

Sample

InputOutput
1
5 10
1 1 2
1 3 4
1 1 3
1 4 5
3 2 3
2 5
1 4 5
2 5
3 4 2
3 1 5
Case 1:
4
1
5
2
2

Notes:
After executing the 1st query, the teams are: [1,2], [3], [4], [5].
After executing the 2nd query, the teams are: [1,2], [3,4], [5].
After executing the 3rd query, the teams are: [1,2,3,4], [5].
After executing the 4th query, the only one team is: [1,2,3,4,5].
The 5th query is the checking operation. Assignment operation in the 3rd query is the 1st valid assignment operation in which student 2 becomes the member of the team of size >= 3. There is only one valid assignment operation after the 3rd query till this checking operation and that is in the 4th query. This only one assignment operation will be canceled out.
So, the reformed teams will be: [1,2,3,4], [5]. The size of the current team of student 2 is = 4.
After executing the 7th query, the only one team is: [1,2,3,4,5].
The 9th query is a checking operation. Valid assignment operations in the 3rd and the 7th queries will be canceled out. The reformed teams will be: [1,2], [3,4], [5].
In the 10th query, as the size of the student 1’s current team [1,2] is 2 which is already less than 5, Ben will do nothing.


Discussion

Statistics


100% Solution Ratio

EgorKulikovEarliest, Jan '20

EgorKulikovFastest, 0.2s

Tashdid_trdbLightest, 4.2 MB

rebornShortest, 1663B

Submit

Login to submit

Editorial

Observing the constraints, it’s pretty obvious that approximate O(n × log(n)) solution is needed to ...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.