Problem D
Spårvagnar på vift

I staden Blöteborg är spårvagnar det bästa sättet att ta sig fram. Blöteborgs spårvägsnät har dock vissa brister, till exempel kan inte spårvagnarna backa eftersom de bara har förarhyttar i ena änden. Detta är ett särskilt stort problem eftersom spårvägsnätet bildar ett träd, dvs att det inte finns några cykler i nätet. För att inga spårvagnar ska bli strandade någonstans har dock Blöteborg byggt vändslingor i alla trädets lövnoder så spårvagnarna kan vända på sig där. Eftersom lövnoderna är de enda platserna en spårvagn kan vända på är alla spårvägsnätets ändhållplater i lövnoder.

Blöteborgs spårvagnsresenärer är inte alltid uppmärksamma på var spårvagnen är på väg, så när en spårvagn kör fel kan det upptäckas var som helst mellan felkörningen och att spårvagnen kommer fram till fel ändhållplats. Men när en Blöteborgare väl märker att spårvagnen har kört fel skickar de alltid in ett formellt klagomål till Bästtrafik och är så högljudda att alla andra vet att ett klagomål redan är inskickat och att de inte behöver skicka in ett till. Kalabaliken får också föraren att vakna till ordentligt och garantera att spårvagnen vänder i närmaste möjliga vändslinga.

Bästtrafik, som är ansvariga för att köra spårvagnarna, har precis fått in årets felrapport. Det har kommit in totalt $Q$ stycken klagomål från resenärer där spårvagnen har åkt fel. Varje sådant klagomål säger vid vilken station felkörningen upptäcktes och vilka ändhållplatser spårvagnen var på väg mellan innan den körde fel. Kan du hjälpa Bästtrafik räkna ut hur mycket längre spårvagnen fick köra vid varje felkörning?

Indata

Den första raden indata består två heltal $N$ och $Q$ ($2 \leq N \leq 2 \cdot 10^5, 1 \leq Q \leq 10^5$), antalet hållplatser och antalet klagomål. Sedan följer $N-1$ rader med två heltal $a$ och $b$, vilket innebär att hållplatserna $a$ och $b$ är direkt sammankopplade. Till sist kommer $Q$ rader med klagomål som består av tre heltal $n, s_1$ och $s_2$, vilken hållplats resenären är på och vilka ändhållplatser hens spårvagn var på väg mellan. Det är garanterat att spårvagnen var på väg bort från sin korrekta väg när klagomålet skickades in, och den kunde alltså köra vidare från hållplats $n$ åt alla håll utom det den kom ifrån (om det inte är en ändhållplats, då kan den bara köra tillbaka samma väg). Alla hållplatser är beskrivna som heltal mellan $1$ och $N$.

Utdata

Skriv ut $Q$ rader med ett heltal vardera, hur mycket längre spårvagnarna behövde köra för varje klagomål i rapporten, i samma ordning som i indatan.

Poängsättning

Din lösning kommer att testas på flera olika testgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring

I exempelfall två kör spårvagnen först mellan nod $1$ och nod $4$ och har hamnat i nod $5$. Det innebär att den måste ha kört fel i nod $2$. Den närmsta ändhållplatsen från nod $5$ är nod $6$. Avståndet mellan nod $2$ och nod $6$ är två, vilket innebär att spårvagnen totalt behöver köra $4$ stationer extra. Den andra spårvagnen åker mellan nod $4$ och nod $6$ och har hamnat i nod $7$. Det innebär att den körde fel i nod $3$. Eftersom $7$ är en ändhållplats ska vi beräkna avståndet mellan nod $3$ och nod $7$, vilket är $1$. Det innebär att spårvagnen åkte $2$ stationer extra.
I exempelfall tre ska spårvagnen åka mellan nod $1$ och nod $4$ men har hamnat i nod $6$. Det innebär att den körde fel i nod $2$. Eftersom närmsta ändhållplatsen är nod $9$ behöver vi beräkna avståndet mellan nod $2$ och nod $9$. Det är $4$, vilket innebär att spårvagnen totalt behöver åka $8$ stationer extra.

Figure 1: Hur spårvägsnätverket ser ut i exempelfall $3$.

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

8

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

4
2

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

10