Bosses

The year is 2025. In the past decade, Xorin's efforts genuinely payed off, especially considering that he and Xoranna are now happily married. Furthermore, our dear friend is now a successful employee at a Fortune 500 company.

As terrific as he may be at his job, Xorin still requires Xoranna's help. She agreed to help him intervene and settle any conflicts that may arise between the company's employees.

The internal hierarchy can be considered an undirected tree. The CEO may change at any moment, meaning that the tree suffers a re-rooting. Therefore, Xoranna must be able to face two kinds of events:

• change(x) - employee x becomes the CEO
• conflict(x, y) - a conflict arises between employees x and y

Xoranna has already prepared for these situations. Whenever two employees get in a conflict, she delegates their closest common boss to address the issue. If any of the employees involved is the other's boss (direct or indirect), Xoranna will personally step in and solve their problem. Your task is to help Xoranna decide whom to assign to each matter.

Input

The first line of the input contains two integers n and m, representing the number of employees and the number of tasks, respectively.

The following n-1 lines contain the hierarchy's edges, in no particular order.

The following m lines contain the events, structured in the following manner:

• 1 x - describing a change(x) event
• 2 x y - describing a conflict(x, y) event

Output

You should output one line for each conflict in the given input. The answer should be either the employee that will have to solve the issue, or -1, in case Xoranna personally steps in.

Constraints

• 1 ≤ n, m ≤ 105
• Initially, employee number 1 is the CEO of the company.
• No employee has multiple personality disorder, so one cannot encounter a conflict with himself.

InputOutput
11 11
1 2
3 1
4 2
5 2
6 2
7 4
8 4
9 6
10 3
11 3
2 10 11
2 8 9
2 5 11
2 5 6
2 4 2
1 3
2 1 10
2 4 6
2 9 1
1 4
2 9 10
3
2
1
2
-1
3
2
-1
2
Questions?