Le réseau routier de Bytown comprend $n$ intersections et $n-1$ rues bidirectionnelles, chaque rue reliant directement une paire d'intersections, et il est possible de se rendre de n'importe quelle intersection à n'importe quelle autre. Afin d'améliorer le trafic, le maire Byteasar souhaite construire un système de métro. Plus précisément, il souhaite installer des stations de métro à certaines intersections et poser des voies ferrées traversant certaines rues. Le réseau de métro doit être connexe, c'est-à-dire que les trains doivent pouvoir circuler entre deux stations de métro quelconques, en passant éventuellement par d'autres stations.

Le coût de creusement des tunnels est élevé, mais le coût de construction des stations terminales (c'est-à-dire les stations où n'arrive qu'un seul tunnel) est encore plus élevé, car ces stations nécessitent des infrastructures supplémentaires pour le stationnement et l'entretien des trains. En raison de contraintes budgétaires, le nombre de stations terminales peut être au maximum de $k$. D'un autre côté, un réseau de métro raisonnable nécessite au moins deux stations de ce type.

L'« indice d'irritation » des passagers est défini comme le nombre minimal de rues qu'ils doivent parcourir à pied depuis leur domicile pour atteindre la station de métro la plus proche. Le maire demande de concevoir un réseau de métro afin de minimiser la valeur maximale de l'indice d'irritation de tous les passagers. Nous supposons que des passagers habitent à chaque intersection.

Entrée

La première ligne contient deux entiers $n$ et $k$ ($n \ge 3, 2 \le k \le n$), séparés par un espace, représentant respectivement le nombre d'intersections et le nombre maximal de stations terminales. Les intersections sont numérotées de $1$ à $n$.

Les $n-1$ lignes suivantes contiennent chacune deux entiers $a$ et $b$ ($1 \le a, b \le n, a \neq b$), séparés par un espace, indiquant qu'il existe une rue reliant directement les intersections $a$ et $b$.

Sortie

La première ligne doit afficher deux entiers $r$ et $s$, séparés par un espace, représentant respectivement la valeur minimale de l'indice d'irritation maximal des passagers, et le nombre de stations terminales dans cette configuration (satisfaisant $2 \le s \le k$). La deuxième ligne doit afficher $s$ entiers distincts, compris entre $1$ et $n$, correspondant aux numéros des intersections où sont situées les stations terminales.

Parmi toutes les conceptions de réseau, la priorité doit être donnée à celle minimisant $r$. En cas d'égalité, l'objectif secondaire est de minimiser $s$. S'il existe plusieurs conceptions satisfaisant les critères de $r$ minimal et $s$ minimal, n'importe laquelle d'entre elles peut être affichée.

Exemples

Exemple 1

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

Sortie 1

1 2
8 1

Remarque

Le réseau routier est illustré ci-dessous. La conception optimale du réseau de métro comporte deux stations terminales (situées aux intersections 1 et 8). L'indice d'irritation maximal des passagers correspondant est de 1. Notez qu'il existe d'autres conceptions optimales du réseau de métro satisfaisant $r=1$ et $s=2$. Il existe également des réseaux avec $r=1$ et $s=3$, mais ils ne sont pas optimaux.

Tests d'exemple

• 1ocen: $n = 30, k = 29$, les intersections $2, \dots, n$ sont toutes reliées à l'intersection $1$.
• 2ocen: $n = 5000, k = 4000$, les intersections $1, 2, \dots, 2000$ forment un chemin, les intersections $2001, \dots, 3500$ sont toutes reliées à l'intersection $1$, et les intersections $3501, \dots, 5000$ sont toutes reliées à l'intersection $2000$.
• 3ocen: $n = 2^{20} - 1, k = 1509$, les intersections forment un arbre binaire complet.

Notation

Les jeux de tests sont composés des sous-tâches suivantes. Chaque sous-tâche peut contenir plusieurs points de test. Si le programme ne donne que la première ligne correcte, il obtiendra 50 % des points pour ce point de test. N'oubliez pas que le programme doit toujours se terminer normalement et ne pas dépasser les limites de temps et de mémoire. Les limites de temps pour chaque sous-tâche sont publiées sur SIO.