En Byteotia hay $n$ ciudades, numeradas del $1$ al $n$, y $n-1$ carreteras, cada una conectando directamente dos ciudades. Desde cada ciudad, es posible llegar a cualquier otra ciudad de exactamente una manera sin retroceder.

Usted está a cargo de la contrainteligencia de Byteotia. ¡Acaba de recibir información de que espías de la hostil Bitotia se han infiltrado en algunas ciudades! Usted sabe que los espías bitotianos siempre operan en parejas. Cuando un espía de una pareja descubre información útil, intenta llegar a la ciudad donde se encuentra el segundo espía para compartir sus hallazgos. Para cada una de las $q$ parejas de espías, usted sabe exactamente en qué ciudades se encuentran actualmente los espías de esa pareja.

Su tarea es asegurarse de que ninguna pareja de espías pueda reunirse. Para lograr esto, puede declarar una cuarentena en cualquier conjunto de ciudades. Está prohibido entrar, pasar a través o salir de una ciudad bajo cuarentena.

Los espías que forman una pareja pueden reunirse si y solo si existe una secuencia de ciudades $x_1, x_2, \dots, x_k$, ninguna de las cuales ha sido puesta bajo cuarentena, tal que $x_1$ es la ciudad donde se encuentra un espía, $x_k$ es la ciudad donde se encuentra el otro espía, y para cada $1 \le i \le k-1$, las ciudades $x_i$ y $x_{i+1}$ están conectadas directamente por una carretera.

Naturalmente, usted no desea paralizar todo el país, por lo que desea poner la menor cantidad posible de ciudades bajo cuarentena. Su tarea es calcular el número mínimo de ciudades que deben ponerse bajo cuarentena para evitar que todas las parejas de espías se reúnan. Además, debe proporcionar cualquier lista de ciudades de longitud mínima que deban ponerse bajo cuarentena para lograr esto.

Representación de las parejas de espías A, B y C en el grafo de ciudades.

Entrada

La primera línea de la entrada contiene dos enteros $n$ y $q$ ($2 \le n \le 5 \cdot 10^5$, $1 \le q \le 5 \cdot 10^5$), que representan el número de ciudades en Byteotia y el número de parejas de espías, respectivamente.

Las siguientes $n-1$ líneas contienen la descripción de las carreteras. La $i$-ésima línea (para $1 \le i \le n-1$) contiene dos enteros $a_i$ y $b_i$ ($1 \le a_i, b_i \le n$, $a_i \neq b_i$), lo que significa que las ciudades $a_i$ y $b_i$ están conectadas directamente por una carretera.

Las siguientes $q$ líneas contienen la descripción de las parejas de espías. La $i$-ésima línea (para $1 \le i \le q$) contiene dos enteros $c_i$ y $d_i$ ($1 \le c_i, d_i \le n$, $c_i \neq d_i$), que representan las ciudades donde se encuentra la $i$-ésima pareja de espías. Varios espías (de diferentes parejas) pueden estar en la misma ciudad.

Salida

La primera línea de la salida debe contener un solo entero $s$, que representa el número mínimo de ciudades que deben ponerse bajo cuarentena para evitar que todas las parejas de espías se reúnan. La segunda línea debe contener $s$ enteros que representen las ciudades que deben ponerse bajo cuarentena para lograr esto.

Ejemplos

Entrada 1

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

Salida 1

2
2 3

Nota

Hay tres parejas de espías, denotadas en la figura por las letras $A$, $B$ y $C$. Si las ciudades $2$ y $3$ (marcadas con círculos) se ponen bajo cuarentena, ninguna pareja de espías puede reunirse sin visitar una de estas ciudades. Otras listas válidas de ciudades para poner bajo cuarentena incluyen, por ejemplo, $1$ y $3$, o $1$ y $7$.

Testy przykładowe

El test 0a es el ejemplo anterior. Además: - 0b: $n = 10, q = 5$. - 0c: $n = 500\,000, q = 250\,000$, estructura de camino, parejas definidas por fórmulas. - 0d: $n = 262\,143, q = 17$, estructura de árbol binario, parejas definidas por fórmulas. - 0e: $n = 500\,000, q = 499\,999$, estructura de estrella, parejas definidas por fórmulas.

Ocenianie

El conjunto de pruebas se divide en los siguientes subproblemas:

Si solo la primera línea de su respuesta es correcta, su solución obtendrá el 80% de los puntos para ese caso de prueba. No es necesario imprimir la segunda línea para obtener estos puntos.