Description

Disjoint set is a beautiful data structure. In this quiz, you need to implement 3 operations.

1 p q	Union the sets containing p and q. If p and q are in the same set, do nothing.
2 p q	Move p to the set containing q. If p and q are in the same set, do nothing.
3 p	Print the number of elements and the sum of elements in the set containing p.

Initially, there are n sets. {1}, {2}, {3},......., {n} 

 

Example:

Initialization: {1}, {2}, {3}, {4}, {5}

After operation 1 1 2: {1, 2}, {3}, {4}, {5}

After operation 1 3 4: {1, 2}, {3, 4}, {5}

After operation 2 2 5: {1}, {3, 4}, {2, 5}

After operation 1 1 5: {3, 4}, {1, 2, 5}

 

Hint:

The move-operation is a little difficult in the tree representation. If you have no idea about it, you can take the following method as a reference.

Method: When moving an element to another set, you should map this element to a new element.

               And for all operations after that, use the new element instead of the old one.

Example:

Note:

Time is limited, you should find out an efficient implementation.

You are not allowed to use STL.

Input

The input will contain one or more testcases.

Each testcase begins with a line containing two integers n and m, the number of sets, and the number of commands.

Each of the next m lines contains a command.

1 <= n, m <= 100000

1 <= p, q <= n

Output

For each type-3 command, output the number of elements and the sum of elements separated by one space.

Followed by a newline character '\n'.

Sample Input  Download

Sample Output  Download

Tags

Discuss