Después de manipular la elección de la nación ardilla y obtener el control total sobre la nación, Ardilla174 ha ordenado el encarcelamiento de su enemigo Ardilla932, (las ardillas no fueron lo suficientemente creativas para inventar nombres propios).

Para recuperar su autoridad y poder, Ardilla932 necesita escapar de la prisión. Poco sabe Ardilla174, que Ardilla932 tiene un cómplice (usted) que tiene acceso al sistema de vigilancia de la prisión, que ayudará a Ardilla932 a escapar de la prisión de manera segura sin encontrarse con ningún guardia.

La prisión tiene ~N~ habitaciones etiquetadas de ~1~ a ~N~, con ~N - 1~ pasillos de dos vías que conectan pares de habitaciones, con el pasillo \(i ^ {ésima}\) que conecta la habitación ~x_i~ y ~y_i~. Es posible viajar entre cualquier par de habitaciones utilizando una serie de pasillos, y se puede demostrar que el camino más corto entre dos habitaciones es único. La seguridad es muy estricta, con guardias patrullando una serie de habitaciones conectadas con pasillos. Chocar con cualquier guardia resultará en un castigo severo, por lo que planificar la fuga será una necesidad.

Ardilla932 le hará preguntas ~Q~ en forma de dos pares de números enteros ~(a_i, b_i)~ y ~(c_i, d_i)~, que le preguntará si es seguro o no, y la primera vez que se encontrará un guardia si viaja de la habitación ~a_i~ a la habitación ~b_i~ y el guardia se mueve de la habitación ~c_i~ a la habitación ~d_i~. Tanto Ardilla932 como el guardia usan el camino más corto entre las dos habitaciones, y solo se encontrarán si ambos están en la misma habitación al mismo tiempo y ninguno de ellos ha llegado a su habitación de destino todavía. Ambos abandonan su habitación inicial en el tiempo ~t = 0~ y tardan ~1~ segundo en trasladarse a una habitación adyacente.

A Ardilla932 se le acaba el tiempo, ¿puede responder rápidamente a todas sus preguntas?

Restricciones

• ~2 \le N \le 200 000~, ~1 \le Q \le 200 000~

• ~1 \le x_i, y_i \le N~ para todo ~1 \le i \le N - 1~

• ~1 \leq a_i, b_i, c_i, d_i \leq N~ para todo ~1 \leq i \leq Q~

• ~a_i \neq b_i~ para todo ~1 \le i \le Q~

• ~c_i \neq d_i~ para todo ~1 \le i \le Q~

Solo se permite la entrada donde sea posible viajar entre cualquier par de habitaciones usando una serie de pasillos.

Subtareas

Subtarea 1 [10%]

• ~2 \le N \le 2000~

• ~1 \le Q \le 2000~

Subtarea 2 [18%]

• ~x_i = i~ para todo ~1 \le i \le N - 1~

• ~y_i = i + 1~ para todo ~1 \le i \le N - 1~

Subtarea 3 [18%]

• ~a_i = 1~ para todo ~1 \le i \le Q~

• ~b_i = N~ para todo ~1 \le i \le Q~

• ~d_i = N~ para todo ~1 \le i \le Q~

Subtarea 4 [18%]

• ~a_i = 1~ para todo ~1 \le i \le Q~

• ~b_i = N~ para todo ~1 \le i \le Q~

Subtarea 5 [16%]

• ~b_i = N~ para todo ~1 \le i \le Q~

• ~d_i = N~ para todo ~1 \le i \le Q~

Subtarea 6 [20%]

Sin restricciones adicionales.

Especificación de entrada

La primera línea de entrada contiene 2 números enteros, ~N~ y ~Q~, que representan el número de habitaciones en la prisión y el número de preguntas que formula Ardilla932.

Las siguientes ~N - 1~ líneas describen los pasillos. Cada línea contiene ~2~ enteros, ~x_i~ y ~y_i~, lo que indica un pasaje de dos vías entre las habitaciones ~x_i~ y y ~y_i~. Solo se permite la entrada donde sea posible viajar entre cualquier par de habitaciones usando una serie de pasillos.

Las siguientes ~Q~ líneas describen las preguntas que formula Ardilla932. Cada línea contiene 4 ​​enteros, ~a_i~, ~b_i~, ~c_i~ y ~d_i~, lo que indica que Ardilla932 está preguntando si es seguro o no, y la primera vez que se encontrará con un guardia si viaja de la habitación ~a_i~ a la habitación ~b_i~ y el guardia se mueve de la habitación ~c_i~ a la habitación ~d_i~.

Especificación de salida

Imprima ~Q~ líneas. La línea \(i ^ {ésima}\) debe contener la respuesta a la \(i ^ {ésima}\) pregunta. Si Ardilla932 se encuentra con un guardia si viaja de la habitación ~a_i~ a la habitación ~b_i~ y el guardia se mueve de la habitación ~c_i~ a la habitación ~d_i~, imprima un entero único igual a la primera vez que se encontrará con el guardia. De lo contrario, imprima ~-1~.

Ejemplos

Entrada de muestra 1

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

Salida de muestra 1

1
-1
-1
-1

Explicación de la muestra 1

Para la primera pregunta, Ardilla932 se encontrará con el guardia en ~tiempo = 1~ en la habitación ~5~.

Para las preguntas segunda, tercera y cuarta, Ardilla932 no se encontrará con el guardia antes de que al menos uno de ellos llegue a su destino.

Entrada de muestra 2

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

Salida de muestra 2

-1
-1
1

Entrada de muestra 3

6 2
5 4
4 3
2 3
3 6
1 2
1 6 4 6
1 6 5 6

Salida de muestra 3

-1
2

Entrada de muestra 4

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

Salida de muestra 4

0
2

Entrada de muestra 5

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

Salida de muestra 5

1
-1