Mỗi ngày Farmer John vắt sữa tám con bò: Bessie, Buttercup, Belinda, Beatrice, Bella, Blue, Betsy, Sue.

Chúng khá kén chọn và yêu cầu thứ tự đáp ứng $N$ ràng buộc ($1 \leq N \leq 7$). Mỗi ràng buộc là “$X$ phải vắt cạnh $Y$”, tức $X$ ngay trước hoặc ngay sau $Y$.

Tìm thứ tự đáp ứng tất cả ràng buộc. Luôn có. Nếu nhiều, chọn thứ tự đầu theo bảng chữ cái: tên đầu nhỏ nhất trong các con có thể đứng đầu một thứ tự hợp lệ, rồi tên thứ hai nhỏ nhất trong các thứ tự có cùng con đầu, cứ thế.

Dữ liệu vào

Dòng đầu chứa $N$. $N$ dòng tiếp chứa câu X must be milked beside Y, với $X$, $Y$ là tên trong tám con trên.

Dữ liệu ra

In thứ tự hợp lệ trên 8 dòng, mỗi dòng một con. Nếu nhiều, in thứ tự đầu theo bảng chữ cái.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

Beatrice
Sue
Belinda
Bessie
Betsy
Blue
Bella
Buttercup

Ghi công bài toán: Brian Dean