Chaque jour, Farmer John trait ses huit vaches : Bessie, Buttercup, Belinda, Beatrice, Bella, Blue, Betsy, Sue.

Elles sont difficiles et exigent $N$ contraintes ($1 \leq N \leq 7$) sur l’ordre de traite. Chacune dit « $X$ doit être traite à côté de $Y$ » : $X$ doit suivre ou précéder immédiatement $Y$.

Trouvez un ordre satisfaisant toutes les contraintes. Il en existe toujours un. S’il y en a plusieurs, choisissez le premier alphabétiquement : le premier nom est le plus petit parmi les premières vaches possibles, puis le deuxième est le plus petit parmi les ordres valides avec cette première, et ainsi de suite.

Entrée

La première ligne contient $N$. Les $N$ suivantes ont une phrase X must be milked beside Y, où $X$ et $Y$ sont des noms parmi les huit ci-dessus.

Sortie

Affichez sur 8 lignes, une vache par ligne, un ordre satisfaisant toutes les contraintes. Si plusieurs conviennent, affichez le premier alphabétiquement.

Exemples

Entrée 1

3
Buttercup must be milked beside Bella
Blue must be milked beside Bella
Sue must be milked beside Beatrice

Sortie 1

Beatrice
Sue
Belinda
Bessie
Betsy
Blue
Bella
Buttercup

Crédits du problème : Brian Dean