P5558 Heartfelt Autumn

Windingly passing through others’ lips and teeth. How many days and nights have I heard your story. Could it be that this one word, “love,” Cannot be understood even if one throws away life and death. I heard that city in the northern land, Is covered by winter snow all day long. By the time old friends part forever and walk farther and farther away, In the blink of an eye, it is already two lifetimes apart. Who goes from life to death, who worries about gain and loss, There is not much time left even to look at each other. The person in the painting secretly—his heart sways and his spirit is lost. A drop of tears blurs the whole page. Waving ink to draw eyebrows and eyes, lifting the brush to trace the hair at the temples. With just a few strokes, it turns out to be like this. At midnight where no one is, unrolling the scroll to the moon, Suddenly I understand this longing. Whose signature wrote the name. ———— “Heartfelt Autumn” # Background In the first month of the first year of Jingning (33 BC), the night before Zhaojun left for the frontier. The painter stumbled and crashed as he came to the palace where Zhaojun lived. > I heard that city in the northern land > Is covered by winter snow all day long > By the time old friends part forever and walk farther and farther away > In the blink of an eye, it is already two lifetimes apart > —— “Heartfelt Autumn” If they could never meet again, the painter thought, he wanted to leave something for Zhaojun. He wanted to give his paintbrush to Zhaojun. **There are $N$ rooms in Zhaojun’s palace, connected by $N-1$ roads.** **The painter is now in the entrance hall room $S$. He vaguely remembers that Zhaojun’s room is number $T$.** Outside the window, the wind and rain rage. Inside the palace it flickers between light and dark, and there is not a single shadow of a person. The painter walks into the dim corridor. On the wall of each corridor, there are several maple leaves painted—these were painted earlier at Zhaojun’s request. Zhaojun said she especially liked autumn, and especially the maple leaves of autumn. > How many past events did we talk about side by side—before we knew it, dusk had arrived. > —— “Heartfelt Autumn” The corridor is extremely dark. The painter wants to light the candles prepared inside. He remembers Zhaojun had a habit: **in each corridor, the number of candles equals the number of maple leaves on the wall. If Zhaojun wants to light the candles in a corridor, she will light them all. At that moment, Zhaojun considers that corridor to be lit up, and she will not light up any corridor whose number of maple leaves is less than that corridor’s**. This should be the last time coming to this place, the painter thought. He wants to follow Zhaojun’s habit and walk to Zhaojun’s room. At the same time, the painter does not want to go back the way he came, so he will not take any corridor he has already walked through. **Now the painter wants to know: when he walks from the palace hall $S$ to Zhaojun’s room $T$, without going back, what is the maximum number of corridors he can light up?**

In the first month of the first year of Jingning (33 BC), the night before Zhaojun left for the frontier. The painter stumbled and crashed as he came to the palace where Zhaojun lived. > I heard that city in the northern land > Is covered by winter snow all day long > By the time old friends part forever and walk farther and farther away > In the blink of an eye, it is already two lifetimes apart > —— “Heartfelt Autumn” If they could never meet again, the painter thought, he wanted to leave something for Zhaojun. He wanted to give his paintbrush to Zhaojun. **There are $N$ rooms in Zhaojun’s palace, connected by $N-1$ roads.** **The painter is now in the entrance hall room $S$. He vaguely remembers that Zhaojun’s room is number $T$.** Outside the window, the wind and rain rage. Inside the palace it flickers between light and dark, and there is not a single shadow of a person. The painter walks into the dim corridor. On the wall of each corridor, there are several maple leaves painted—these were painted earlier at Zhaojun’s request. Zhaojun said she especially liked autumn, and especially the maple leaves of autumn. > How many past events did we talk about side by side—before we knew it, dusk had arrived. > —— “Heartfelt Autumn” The corridor is extremely dark. The painter wants to light the candles prepared inside. He remembers Zhaojun had a habit: **in each corridor, the number of candles equals the number of maple leaves on the wall. If Zhaojun wants to light the candles in a corridor, she will light them all. At that moment, Zhaojun considers that corridor to be lit up, and she will not light up any corridor whose number of maple leaves is less than that corridor’s**. This should be the last time coming to this place, the painter thought. He wants to follow Zhaojun’s habit and walk to Zhaojun’s room. At the same time, the painter does not want to go back the way he came, so he will not take any corridor he has already walked through. **Now the painter wants to know: when he walks from the palace hall $S$ to Zhaojun’s room $T$, without going back, what is the maximum number of corridors he can light up?**

The first line contains an integer $N$, meaning the number of rooms in the palace. Next there are $N-1$ lines. Each line contains three integers $u_{i}, v_{i}, leaf_{i}$, meaning there is a corridor between $u$ and $v$, and there are $leaf_{i}$ maple leaves painted in that corridor. Next is an integer $M$. The last $M$ lines each contain two integers $S_{i}, T_{i}$.

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

## Constraints | Test ID | N | M | Special Properties | | :----------: | :----------: | :----------: | :----------: | | $1$ | $100$ | $100$ | None | | $2$ | $100$ | $100$ | None | | $3$ | $100$ | $1000$ | None | | $4$ | $10000$ | $10000$ | None | | $5$ | $10000$ | $10000$ | $1$ | | $6$ | $10000$ | $10000$ | $1,2$ | | $7$ | $10000$ | $10000$ | $1,2$ | | $8$ | $30000$ | $100000$ | None | | $9$ | $30000$ | $100000$ | None | | $10$ | $30000$ | $300000$ | None | Special property $1$: $1