Caminando entre Pastizales.
Las vacas convenientemente numeradas ... están pastando entre los pastizales también numerados convenientemente .... Aún más, la vaca está pastando en el pastizal .
Algunos pares de pastizales están conectados por senderos bidireccionales que pueden ser recorridos por las vacas. El sendero conecta los pastizales y y tiene una longitud de .
Los senderos están organizados de manera tal que entre cualesquiera dos pastizales distintos, existe un camino de senderos que va entre ellos. Por lo tanto, los senderos forman un árbol.
Las vacas son muy sociales y quieren visitarse entre ellas frecuentemente. Siempre apuradas, ellas quieren que usted les ayude a planificar sus visitas calculando las longitudes de caminos entre pares de pastizales (cada par está dado como una pregunta .
Entrada
Línea 1: Dos enteros separados por espacio: y .
Líneas 2..N: La línea contiene tres enteros separados por espacios: , y .
Líneas N+1..N+Q: Cada línea contiene dos enteros separados por espacio representando dos pastizales distintos entre los cuales las vacas quieren viajar: y .
Salida
Líneas 1..Q: La línea contiene la longitud del camino entre los dos pastizales en la pregunta .
Ejemplo de Entrada
4 2
2 1 2
4 3 2
1 4 3
1 2
3 2
Ejemplo de Salida
2
7
Explicación
Pregunta 1: El sendero entre los pastizales y tiene longitud .
Pregunta 2: Viaje a través del sendero entre los pastizales y , luego a través del que está entre y , y finalmente a través del que está entre y , para una longitud total de .
Comments