يحلب Farmer John كل يوم أبقاره الثماني: Bessie, Buttercup, Belinda, Beatrice, Bella, Blue, Betsy, Sue.

الأبقار انتقائية وتطلب $N$ قيود ($1 \leq N \leq 7$) على الترتيب. كل قيد يقول «يجب حلب $X$ بجانب $Y$»، أي تكون $X$ قبل $Y$ مباشرة أو بعدها مباشرة.

ابحث عن ترتيب يحقق جميع القيود. مضمون وجوده. إن تعددت الحلول فأخرج الأول أبجديًا: أصغر اسم بين الأبقار الممكنة أولًا في ترتيب صالح، ثم أصغر اسم ثاني بين الترتيبات الصالحة بهذه الأولى، وهكذا.

الإدخال

السطر الأول يحتوي $N$. الأسطر $N$ التالية في كل منها الجملة X must be milked beside Y، حيث $X$ و$Y$ اسمان من الثمانية أعلاه.

الإخراج

أخرج ترتيبًا صالحًا في 8 أسطر، بقرة في كل سطر. إن تعددت فأخرج الأول أبجديًا.

أمثلة

الإدخال 1

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

الإخراج 1

Beatrice
Sue
Belinda
Bessie
Betsy
Blue
Bella
Buttercup

نسبة المسألة: Brian Dean