URI Online Judge | 3109

Desk Updates

By Cristhian Bonilha, UTFPR BR Brazil

Timelimit: 1

You work at an office with N employees and N desks. All employees and all desks have an id number from 1 to N, and initially each employee is sitting at the desk with the same id as theirs. In other words, employee 1 is sitting at desk 1, employee 2 at desk 2, and so on.

To increase the company's overall productivity, the HR is trying out a variation of Feng Shui at the office, making employees swap desks with each other.

However, the boss sometimes needs to talk with these employees, and he finds it very difficult to keep track of these desk swaps.

It may happen, then, that the boss wants to talk to employee A, so he walks towards desk A, but only to find out that employee C is sitting there. He then assumes that A may be sitting at desk C, so he walks towards desk C. We call this a "redirection", and this can happen several times until the boss finally finds employee A.

In summary, there are two types of events:

You got a taks from HR about assessing how this Feng Shui variation process is helping the company. You have to process Q events. Whenever the event is of type query, you must figure out how many times the boss was redirected until finding employee A. It's guaranteed that he can always find him.


First line of input will have an integer N (2 ≤ N ≤ 103), indicating how many employees and desks there are in the office.

The next line will have an integer Q (1 ≤ Q ≤ 5×103), indicating how many events should be processed.

Following there will be Q lines, each representing an event. Each line will have two or three integers. The first integer is E (1 ≤ E ≤ 2).

If E is equal to 1, the event is of type update, and there will be two more integers A and B (1 ≤ A, BN) where AB.

If E is equal to 2, the event is of type query, and there will be one more integer A.


For each event of type query you must print one line, containing one integer, representing how many times the boss was redirected until finding employee A.

Input Samples Output Samples

2 1
1 1 2
2 1


1 1 2
1 3 1
2 1