The following is a translation of Posea's fable of The Turtle and the Rabbit:

The Rabbit laughed at the Turtle's slower pace.

rabbit: we got gta 6 before you pulled up to the park 💔😭🙏
turtle: sybau gng u pmtfo watch me destroy you in a game of tag 🥀🥀

The meaning of this fable is still a major controversy, especially since Posea never told us what the result of the game was. Your j*b as a programmer is to settle the debate once and for all by simulating rounds of tag!

It is known that the Turtle and the Rabbit played their game of tag in a park with ~N~ clearings and ~N-1~ pathways, where the ~i^{th}~ pathway connects clearing ~a_i~ and ~b_i~ and can be travelled in both directions. It is possible to travel between any two clearings using these pathways, and each pathway has the same unit length.

You will simulate ~Q~ rounds of tag. In the ~i^{th}~ round, if ~t_i = 1~, then the Turtle is the tagger. Otherwise, if ~t_i = 2~, the Rabbit is the tagger. The animal which is not the tagger will be called the runner. The tagger and runner will begin in distinct clearings, ~u_i~ and ~v_i~, respectively, and begin moving simultaneously. The Rabbit can move one pathway per second, while the Turtle can only move one pathway per two seconds. The game ends when the tagger reaches the same clearing as the runner, or meets the runner part of the way along a pathway. The goal of the tagger is to minimize the duration of the game, while the goal of the runner is to maximize it.

Note that motion is continuous and that neither animal simply teleports to the next clearing at discrete points in time, rather, they must travel at their respective speeds along pathways to reach other clearings. The animals can also choose to stay still. You may assume that switching from one pathway to another at a clearing takes negligible time.

Assuming that the Turtle and the Rabbit move optimally to achieve their assigned goals, what will be the duration of each simulated round of tag?

Constraints

~2 \le N \le 2 \times 10^5~
~1 \le Q \le 2 \times 10^5~

~1 \le a_i, b_i \le N~
~a_i \neq b_i~

~t_i \in \{1, 2\}~
~1 \le u_i, v_i \le N~
~u_i \neq v_i~

It is possible to travel between any two clearings using the pathways.

Subtask 1 [20%]

~u_i = 1~
~t_i = 1~

Subtask 2 [30%]

~t_i = 1~

Subtask 3 [50%]

No additional constraints.

Input Specification

The first line contains two space-separated integers, ~N~ and ~Q~, the number of clearings in the park and the number of rounds of tag, respectively.

The next ~N-1~ lines each contain two space-separated integers, ~a_i~ and ~b_i~, indicating that the ~i^{th}~ pathway connects clearing ~a_i~ and ~b_i~ in both directions.

The next ~Q~ lines each contain three space-separated integers describing the ~i^{th}~ round of tag, ~t_i~, ~u_i~, and ~v_i~, the number indicating which animal is the tagger, the initial clearing of the tagger, and the initial clearing of the runner. If ~t_i = 1~, the Turtle is the tagger in this round. If ~t_i = 2~, the Rabbit is the tagger.

Output Specification

Output ~Q~ lines, the ~i^{th}~ line containing one integer, the duration of the ~i^{th}~ round of tag, assuming that the Turtle and the Rabbit move optimally to achieve their assigned goals. It can be shown that this value is always an integer.

Sample Input 1

9 3
1 2
1 3
2 4
2 5
3 6
4 7
7 8
8 9
1 3 5
1 7 2
2 9 5

Sample Output 1

12
10
6

Explanation for Sample 1

The park has the following structure:

In the first round of tag, the Turtle is the tagger and the Rabbit is the runner. The Turtle begins at clearing ~3~, while the Rabbit begins at clearing ~5~. The Rabbit's best strategy to maximize the length of the round is to run towards clearing ~9~ and stay there until it is caught by the Turtle after ~12~ seconds.

In the second round of tag, the Turtle is the tagger and the Rabbit is the runner again. The Turtle now begins at clearing ~7~, while the Rabbit begins at clearing ~2~. The Rabbit's best strategy to maximize the length of the round is to run towards clearing ~6~ and stay there until it is caught by the Turtle after ~10~ seconds.

In the third round of tag, the Rabbit is the tagger and the Turtle is the runner. The Rabbit begins at clearing ~9~, while the Turtle begins at clearing ~5~. The Turtle's best strategy to maximize the length of the round is to run constantly towards clearing ~6~. However, the Rabbit is faster than the Turtle and catches it at clearing ~3~, after ~6~ seconds.

Sample Input 2

15 8
1 2
1 3
2 4
2 5
2 6
3 7
4 8
7 9
7 10
8 11
8 12
8 13
9 14
9 15
1 5 8
1 4 5
1 10 14
1 14 15
1 2 6
2 8 10
2 4 6
2 9 5

Sample Output 2

8
12
6
16
2
7
2
6

Explanation for Sample 2

The park has the following structure: