Un árbol tiene \(n\) nodos, numerados de \(0\) a \(n - 1\), y cada arista tiene un peso entre \(1\) y \(26\). Cada consulta da dos nodos \(a\) y \(b\) y pregunta: ¿cuántas aristas del camino entre \(a\) y \(b\) hay que cambiar de peso, como mínimo, para que todas las aristas del camino tengan el mismo peso? Las consultas son independientes: el árbol no cambia entre una y otra.

Entrada

La primera línea tiene \(n\) \((1 \le n \le 10^4)\) y \(q\) \((1 \le q \le 2 \cdot 10^4)\). Siguen \(n - 1\) líneas con las aristas \(u\) \(v\) \(w\) \((1 \le w \le 26)\) y luego \(q\) líneas con las consultas \(a\) \(b\).

Salida

Para cada consulta, una línea con la cantidad mínima de cambios.

Ejemplo 1

Entrada

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

Salida

0
0

Ejemplo 2

Entrada

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

Salida

1
2
2
3