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:
He chooses a student u and a special number x.
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.
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.
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:
1 u v — assign the students u, v (1 ≤ u, v ≤ N, (u ≠ v)) and the members of their teams in a single team.
2 u — print the size of the team student u is currently a member of.
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).
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.
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
Login to submit
Observing the constraints, it’s pretty obvious that approximate O(n × log(n)) solution is needed to ...