Дано неорієнтоване дерево з \(N\) вершин, на кожному з ребер якого містяться по одній маленькій англійській літері.

Шлях між двома вершинами в дереві, відповідає якомусь слову.

Для кожного запиту виду \(U,V\) неохідно порахувати, скільки слів, які починаються з вершини \(U\) будуть лексикографічно менші ніж слово на шляху від \(U\) до \(V\)

Формат вхідних даних

В першому рядку два цілих числа \(N,Q\) (\(1 \le N \le 4000\) , \(1 \le Q \le 500000\))

Кожен з наступних \(N-1\) рядків містить номера вершин які з'єднані ребром, і літеру яка написана на цьому ребрі.

Кожен з наступних \(Q\) рядків містить по два числа \(U,V\) - запит.

Формат вихідних даних

Для кожного запиту, виведіть відповідь

Приклад вхідних даних-1

4 3
4 1 t
3 2 p
1 2 s
3 2
1 3
2 1

Приклад вихідних даних-1

0
1
1

Приклад вхідних даних-2

8 4
4 6 p
3 7 o
7 8 p
4 5 d
1 3 o
4 3 p
3 2 e
8 6
3 7
8 1
4 3

Приклад вихідних даних-2

6
1
3
1

Пояснення до прикладу вихідних даних-2

1. від вершини 8 до вершини 6 на шляху слово popp
є 6 слів, які починаються з вершини 8 і лексикографічно менші за popp
p
po
poo
poe
pop
popd

2. від вершини 3 до вершини 7 на шляху слово "o"
лексикографічно менших за нього, з вершини 3 є лише 1 слово: 
e

3. від вершини 8 до вершини 1 на шляху слово "poo"
лексикографічно менших за нього, з вершини 8 є 3 слова: 
p
po
poe

4. від вершини 4 до вершини 3 на шляху слово "p"
лексикографічно менших за нього, з вершини 4 є лише 1 слово: 
d