Desk Updates

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:

• update A B: the employees A and B swap desks;
• query A: the boss wants to talk to employee A.

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.