parb

Avem un arbore cu $N$ noduri şi rădăcina în nodul $1$, indexat de la $1$ la $N$. Fiecare muchie este etichetată cu o literă.
Pentru două noduri $(x, y)$ unde $x$ este strămoş al lui $y$ definim şirul strămoşesc ca fiind concatenarea muchiilor drumului de la $y$ la $x$.

Cerință

Pe acest arbore se fac $Q$ întrebări, o întrebare are forma unei perechi $(x, y)$ unde x este un strămoş de-al lui $y$. Fie $S$ şirul strămoşesc corespunzător nodurilor $x$ şi $y$.

Pentru fiecare întrebare trebuie să găsiţi câte perechi $(a, b)$ (inclusiv $(x, y)$) dau şirul strămoşesc egal cu $S$.

Date de intrare

Fişierul de intrare parb.in conţine pe prima linie numărul $N$ de noduri, urmat de numărul $Q$ de întrebări. Vor urma $N-1$ linii, fiecare linie va conţine un triplet $(x, y, c)$ reprezentând că există o muchie de la $x$ la $y$ care este etichetată cu caracterul $c$. Urmează $Q$ linii, pe fiecare linie se află câte o pereche $(x, y)$ corespunzătoare unei întrebări.

Date de ieșire

Fişierul de ieşire parb.out va conţine $Q$ linii. Pe linia $i$ se va afla un singur întreg, răspunsul la întrebarea $i$.

Restricții și precizări

• $1 \leq N \leq 100 \ 000$
• $0 \leq Q \leq 100 \ 000$
• Muchiile sunt etichetate cu litere mici ale alfabetului englez.
• Pentru teste în valoare de $20$ puncte, $N \leq 100$.

Exemplu

parb.in

10 4
1 2 m
2 3 m
3 4 c
3 5 c
5 6 l
2 7 c
1 8 c
8 9 m
9 10 c
2 5
1 9
9 10
1 4

parb.out

4
1
5
2