Mỗi ngày, Nông dân John vắt sữa 8 cô bò sữa của mình, tên là Bessie, Buttercup, Belinda, Beatrice, Bella, Blue, Betsy và Sue.

Thật không may, những cô bò khá kén chọn và yêu cầu Nông dân John vắt sữa theo một thứ tự tôn trọng \(N\) ràng buộc (\(1 \leq N \leq 7\)). Mỗi ràng buộc có dạng "\(X\) must be milked beside \(Y\)", quy định rằng bò \(X\) phải xuất hiện trong thứ tự vắt sữa ngay sau bò \(Y\) hoặc ngay trước bò \(Y\).

Hãy giúp Nông dân John xác định một thứ tự các cô bò thỏa mãn tất cả các ràng buộc bắt buộc này. Đề bài đảm bảo luôn tồn tại một thứ tự như vậy. Nếu có nhiều thứ tự hợp lệ, hãy in thứ tự đứng đầu theo thứ tự bảng chữ cái. Nghĩa là, cô bò đầu tiên phải có tên nhỏ nhất theo thứ tự bảng chữ cái trong số tất cả những cô bò có thể đứng đầu ở một thứ tự hợp lệ bất kỳ. Trong tất cả các thứ tự bắt đầu bằng cùng cô bò đứng đầu này, cô bò thứ hai phải có tên nhỏ nhất theo thứ tự bảng chữ cái trong số mọi thứ tự hợp lệ có thể có, và cứ tiếp tục như vậy.

Phân nhóm

Tất cả các test tuân theo các ràng buộc đã nêu.

Dữ liệu vào

Dòng đầu tiên chứa \(N\). Mỗi dòng trong \(N\) dòng tiếp theo chứa một câu mô tả một ràng buộc có dạng "\(X\) must be milked beside \(Y\)", trong đó \(X\) và \(Y\) là tên của một số cô bò của Nông dân John (tám tên có thể có đã được liệt kê ở trên).

Dữ liệu ra

In một thứ tự của các cô bò trên 8 dòng, mỗi dòng một tên bò, sao cho thỏa mãn tất cả các ràng buộc. Nếu có nhiều thứ tự hợp lệ, hãy in thứ tự sớm nhất theo thứ tự bảng chữ cái.

Ví dụ

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

Beatrice
Sue
Belinda
Bessie
Betsy
Blue
Bella
Buttercup

Nguồn

USACO 2019 December Contest, Bronze - Livestock Lineup: https://usaco.org/index.php?page=viewproblem2&cpid=965

Tác giả: Brian Dean.