Les vaches sont envoyées en mission spatiale pour acquérir une nouvelle machine à traire pour leur grange. Elles traversent un amas d’étoiles contenant $N$ planètes ($1 \le N \le 50{,}000$), chacune avec un comptoir commercial.

Elles ont identifié quels types parmi $K$ objets ($1 \le K \le 1{,}000$), numérotés $1..K$, chaque planète désire et quels produits elle propose. Aucune n’a de monnaie : elles pratiquent le troc, chaque partie échangeant exactement un objet (vraisemblablement de types différents).

Les vaches quittent la Terre avec un récipient de foin de qualité (objet 1) et souhaitent une machine à traire (objet $K$). Trouvez la meilleure suite d’échanges sur ces planètes pour obtenir l’objet $K$. Si cela est impossible, affichez -1.

Entrée

• Ligne 1 : deux entiers $N$ et $K$ séparés par un espace.
• Lignes $2..N+1$ : la ligne $i+1$ contient deux entiers $a_i$ et $b_i$ séparés par un espace, les produits échangés de la planète $i$. Elle donne l’objet $b_i$ pour recevoir l’objet $a_i$.

Sortie

• Ligne 1 : le nombre minimal d’échanges pour obtenir la machine, objet $K$, plus un (ou -1 si l’objet $K$ est inaccessible).
• Lignes $2..T+1$ : la liste des objets possédés par les vaches dans l’ordre des échanges.

Exemples

Entrée 1

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

Sortie 1

4
1
3
2
5

Remarque

Détails de la sortie

Les vaches possèdent au total 4 objets : elles échangent d’abord 1 contre 3, puis 3 contre 2, puis 2 contre 5.

Auteurs du problème : Coaches, 2004