En su tiempo libre, el Granjero John ha creado un nuevo servicio para compartir videos, al que llama MooTube. En MooTube, las vacas del Granjero John pueden grabar, compartir y descubrir muchos videos divertidos. Sus vacas ya han subido ~N~ videos ~(1 \leq N \leq 100000)~, convenientemente numerados ~1...N~. Sin embargo, GJ no logra averiguar cómo ayudar a sus vacas a encontrar nuevos videos que les puedan gustar.

GJ quiere crear una lista de "videos sugeridos" para cada video de MooTube. De esta manera, a las vacas se les recomendarán los videos más relevantes para los que ya ven.

GJ diseña una métrica de "relevancia", que determina, como su nombre indica, cuán relevantes son dos videos entre sí. Elige ~N-1~ pares de videos y calcula manualmente su relevancia por pares. Luego, GJ visualiza sus videos como una red, donde cada video es un nodo y los ~N-1~ pares de videos que consideró manualmente están conectados. Convenientemente, GJ ha elegido sus ~N-1~ pares de modo que cualquier video pueda alcanzarse desde cualquier otro video a lo largo de una ruta de conexiones exactamente de una manera. GJ decide que la relevancia de cualquier par de videos debe definirse como la relevancia mínima de cualquier conexión a lo largo de esta ruta.

El Granjero John quiere elegir un valor ~K~ para que, junto a cualquier video dado de MooTube, todos los demás videos con una relevancia de al menos ~K~ respecto a ese video se sugieran. Sin embargo, a GJ le preocupa que se sugieran demasiados videos a sus vacas, lo que podría distraerlas de la producción de leche. Por lo tanto, quiere establecer cuidadosamente un valor apropiado de ~K~. GJ quisiera tu ayuda para responder una serie de preguntas sobre los videos sugeridos para ciertos valores de ~K~.

Entrada

• La primera linea de entrada contiene los números ~N~ y ~Q~. ~(1 \leq Q \leq 100000)~.
• Las siguientes ~N-1~ líneas contienen ~p_i, q_i (1 \leq p_i,q_i \leq N)~ y ~r_i (1 \leq r_i \leq 1000000000)~, indicando que los videos ~p_i~ y ~q_i~ están conectados con relevancia ~r_i~.
• Las últimas ~Q~ líneas describen las ~Q~ preguntas de GJ, cada una contiene dos números: ~k_i~ ~(1 \leq k_i \leq 1000000000)~ y ~v_i~ ~(1 \leq v_i \leq N)~, indicando que GJ quiere saber la cantidad de videos segueridos al ver el video ~v_i~ si ~K = k_i~.

Salida

Imprima ~Q~ líneas. En la línea ~i~, imprima la respuesta a la i-ésima pregunta de GJ.

Ejemplo de Entrada

4 3
1 2 3
2 3 2
2 4 4
1 2
4 1
3 1

Ejemplo de Salida

3
0
2

El Granjero John descubre que los videos ~1~ y ~2~ tienen relevancia ~3~, que los videos ~2~ y ~3~ tienen relevancia ~2~, y que los videos ~2~ y ~4~ tienen relevancia ~4~. Basándose en esto, los videos ~1~ y ~3~ tienen relevancia ~min(3, 2) = 2~, los videos uno y cuatro tienen relevancia ~min(3, 4) = 3~, y los videos ~3~ y ~4~ tienen relevancia ~min(2, 4) = 2~.

El Granjero John quiere saber cuántos videos se sugerirán desde el video ~2~ si ~K=1~, desde el video ~1~ si ~K=3~, y desde el video ~1~ si ~K=4~. Vemos que con ~K=1~, los videos ~1, 3~ y ~4~ se sugerirán en el video ~2~. Con ~K=4~, ningún video se sugerirá desde el video ~1~. Sin embargo, con ~K=3~, los videos ~2~ y ~4~ se sugerirán desde el video ~1~.

USACO 2018 January Contest, Gold Problem 1. MooTube.