Problem Background

Through the words of others,
I've heard countless tales of you.
Is love truly a mystery
That even death cannot unveil?

They say the city in the north
Is covered in snow all day.
When old friends part and drift apart,
It feels like two lifetimes have passed.

Who faces death for life, who fears loss and gain,
We have little time left to share.
The figure in the painting, secretly,
Is captivated and lost in thought.
A single tear blurs the paper.

With ink, I paint the brows, with a brush, the hair,
A few strokes create such a likeness.
In the quiet of the night, under the moon,
I unfold the scroll and suddenly understand this longing.
Who signed their name at the end?

————《Autumn in the Heart》

Problem Description

In the first month of Jingning元年 (33 BC), the night before Wang Zhaojun left for the frontier.

The painter stumbled into the palace where Wang Zhaojun resided.

If we can never meet again, the painter thought, he wanted to leave something for Wang Zhaojun.

He wanted to give her his paintbrush.

There are $N$ rooms in Wang Zhaojun's palace, connected by $N-1$ paths.

The painter is currently in the entrance hall, room $S$, and he vaguely remembers that Wang Zhaojun's room is room $T$.

Outside, the wind and rain rage, the palace is intermittently dark and lit, and there is no one in sight.

The painter enters the dimly lit corridors, where each wall is adorned with several maple leaves, painted by the painter at Wang Zhaojun's request. She loved autumn, especially its maple leaves.

Together, we've shared many stories, and suddenly, dusk has arrived. ——《Autumn in the Heart》

The corridors are pitch dark, and the painter wants to light the candles prepared in the corridors. He remembers Wang Zhaojun's habit: the number of candles in each corridor corresponds to the number of maple leaves on the wall. If Wang Zhaojun wants to light a corridor, she will light all the candles, considering the corridor lit and will not light any corridor with fewer maple leaves than the current one.

This should be the last time I come to this place, the painter thought, he wanted to follow Wang Zhaojun's habit and reach her room.

Now the painter wants to know, from the palace hall $S$ to Wang Zhaojun's room $T$, how many corridors he can light at most.

Input and Output Formats

Input Format

The first line contains a number $N$, representing the number of rooms in the palace.

The next $N-1$ lines each contain three numbers $u_{i}, v_{i}, leaf_{i}$, indicating a path between $u$ and $v$ with $leaf_{i}$ maple leaves.

The next line contains a number $M$.

The last $M$ lines each contain two numbers $S_{i}, T_{i}$.

Output Format

Output $M$ lines, for each pair $S_{i}, T_{i}$, output the maximum number of corridors that can be lit.

Sample Input and Output

Sample Input #1

5
1 2 5
2 3 1
1 4 1
3 5 4
3
2 1
4 2
1 1

Sample Output #1

1
2
0

Sample Input #2

7
1 2 1
1 3 5
2 4 1
4 5 4
5 6 1
1 7 1
5
7 5
7 6
2 7
1 1
2 4

Sample Output #2

4
4
2
0
1

Sample Input #3

20
1 2 1
1 3 3
2 4 5
1 5 1
5 6 5
1 7 5
1 8 4
7 9 1
8 10 2
1 11 1
2 12 5
3 13 1
3 14 3
3 15 3
10 16 1
5 17 1
12 18 5
7 19 4
7 20 5
10
10 3
17 16
11 9
4 6
16 17
11 16
11 11
13 11
2 1
10 11

Sample Output #3

2
3
2
3
3
2
0
2
1
2

Notes

Special Property 1: $1 <= leaf_{i} <= 2$

Special Property 2: $u_{i} + 1 = v_{i}$

For all data, it is guaranteed that $1 <= leaf_{i} <= 5$

Sample 1 Explanation:

Query 1: From room 2 to room 1, the maximum number of corridors that can be lit is 1 (2-1).

Query 2: From room 4 to room 2, the maximum number of corridors that can be lit is 2 (4-1, 1-2).

Query 3: Obviously, no corridors can be lit.

Sample 2 Explanation:

Query 1: From room 7 to room 5, 4 corridors can be lit (7-1, 1-2, 2-4, 4-5).

Query 2: From room 7 to room 6, 4 corridors can be lit (7-1, 1-2, 2-4, 4-5). Not lighting (5-6) because after lighting (4-5), no corridors with fewer maple leaves can be lit, which is optimal, or not lighting (4-5) and lighting (5-6), which is also optimal.

Query 3: From room 2 to room 7, 2 corridors can be lit (2-1, 1-7).

Query 4: No corridors are traversed.

Query 5: 1 corridor is traversed (2-4).

见题面 Input 部分

见题面 Output 部分