À Byteotia, il y a $n$ villes, numérotées de $1$ à $n$, et $n-1$ routes, chacune reliant directement deux villes. Depuis chaque ville, il est possible d'atteindre n'importe quelle autre ville de manière unique sans revenir sur ses pas.

Vous êtes responsable du contre-espionnage byteotien. Vous venez de recevoir l'information que des espions de la Bitotia hostile se sont infiltrés dans certaines villes ! Vous savez que les espions bitotiens opèrent toujours par paires. Lorsqu'un espion d'une paire découvre des informations utiles, il tente de rejoindre la ville où se trouve le second espion pour partager ses découvertes. Pour chacune des $q$ paires d'espions, vous savez exactement dans quelles villes se trouvent actuellement les espions de cette paire.

Votre tâche est de vous assurer qu'aucune paire d'espions ne puisse se rencontrer. Pour y parvenir, vous pouvez déclarer une mise en quarantaine dans n'importe quel ensemble de villes. Il est interdit d'entrer, de traverser ou de quitter une ville en quarantaine.

Les espions formant une paire peuvent se rencontrer si et seulement s'il existe une séquence de villes $x_1, x_2, \dots, x_k$, dont aucune n'a été placée en quarantaine, telle que $x_1$ est la ville où se trouve un espion, $x_k$ est la ville où se trouve l'autre espion, et pour tout $1 \le i \le k-1$, les villes $x_i$ et $x_{i+1}$ sont directement reliées par une route.

Naturellement, vous ne voulez pas paralyser tout le pays, vous souhaitez donc placer le moins de villes possible en quarantaine. Votre tâche est de calculer le nombre minimum de villes qui doivent être placées en quarantaine pour empêcher chaque paire d'espions de se rencontrer. De plus, vous devez fournir une telle liste minimale de villes à placer en quarantaine pour y parvenir.

Entrée

La première ligne de l'entrée contient deux entiers $n$ et $q$ ($2 \le n \le 5 \cdot 10^5$, $1 \le q \le 5 \cdot 10^5$), représentant respectivement le nombre de villes à Byteotia et le nombre de paires d'espions.

Les $n-1$ lignes suivantes contiennent la description des routes. La $i$-ième ligne (pour $1 \le i \le n-1$) contient deux entiers $a_i$ et $b_i$ ($1 \le a_i, b_i \le n$, $a_i \neq b_i$), signifiant que les villes $a_i$ et $b_i$ sont directement reliées par une route.

Les $q$ lignes suivantes contiennent la description des paires d'espions. La $i$-ième ligne (pour $1 \le i \le q$) contient deux entiers $c_i$ et $d_i$ ($1 \le c_i, d_i \le n$, $c_i \neq d_i$), représentant les villes où se trouve la $i$-ième paire d'espions (l'un est dans la ville $c_i$ et l'autre dans la ville $d_i$). Plusieurs espions (de paires différentes) peuvent se trouver dans la même ville.

Sortie

La première ligne de la sortie doit contenir un seul entier $s$, représentant le nombre minimum de villes qui doivent être placées en quarantaine pour empêcher chaque paire d'espions de se rencontrer. La deuxième ligne doit contenir $s$ entiers représentant les villes qui doivent être placées en quarantaine pour y parvenir.

Exemples

Entrée 1

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

Sortie 1

2
2 3

Remarque

Il y a trois paires d'espions, marquées sur le dessin par les lettres $A$, $B$ et $C$. Si les villes $2$ et $3$ sont placées en quarantaine (marquées par des cercles), aucune paire d'espions ne peut se rencontrer sans visiter l'une de ces villes. D'autres listes valides de villes à mettre en quarantaine sont par exemple $1$ et $3$, ou $1$ et $7$.

Tests supplémentaires

Les tests supplémentaires (0b, 0c, 0d, 0e) vérifient les cas limites : - 0a : Test de l'exemple ci-dessus. - 0b : $n=10, q=5$. - 0c : $n=500\,000, q=250\,000$, $a_i=i, b_i=i+1$ pour $1 \le i \le n-1$ (chemin), $c_i = 4 \cdot \lfloor \frac{i-1}{2} \rfloor + 1, d_i = 4 \cdot \lfloor \frac{i-1}{2} \rfloor + 3$ pour $i$ impair, $c_i = 4 \cdot \lfloor \frac{i-1}{2} \rfloor + 2, d_i = 4 \cdot \lfloor \frac{i-1}{2} \rfloor + 4$ pour $i$ pair ($1 \le i \le q$). - 0d : $n=262\,143, q=17, a_i=i+1, b_i=\lfloor \frac{i+1}{2} \rfloor$ pour $1 \le i \le n-1$, $c_i=2^i-1, d_i=2^{18}-2^{18-i}$ pour $1 \le i \le q$. - 0e : $n=500\,000, q=499\,999, a_i=1, b_i=i+1$ pour $1 \le i \le n-1$, $c_i=1, d_i=i+1$ pour $1 \le i \le q$.

Évaluation

Si seule la première ligne de votre réponse est correcte, votre solution recevra 80 % des points pour ce test. Vous n'avez pas besoin de fournir la deuxième ligne pour recevoir ces points.