Mỗi ngày nông dân John vắt sữa 8 con bò của mình, tên Bessie, Buttercup, Belinda, Beatrice, Bella, Blue, Betsy, và Sue.
Tuy nhiên, những con bò này hơi kén chọn và yêu cầu nông dân John phải vắt sữa chúng sao cho mà thỏa mãn ~N~ điều kiện ~(1 \leq N \leq 7)~. Mỗi điều kiện được thể hiện dưới dạng X must be milked beside Y
, nghĩa là bò X phải được vắt sữa ngay trước bò Y hoặc ngay sau bò Y.
Hãy giúp Nông dân John tìm ra một cách sắp xếp những con bò của mình sao cho thỏa mãn điều kiện trên. Đảm bảo luôn tồn tại một cách xếp thỏa mãn. Nếu tồn tại nhiều cách sắp xếp, hãy in cách sắp xếp có thứ tự từ điển bé nhất.
Input
Dòng đầu tiên là số nguyên dương ~N~. ~N~ dòng tiếp theo mô tả một điều kiện dưới dạng X must be milked beside Y
, trong đó X và Y là tên của bò của John (một trong tám cái tên được liệt kê ở trên).
Output
In ra 8 dòng, mỗi dòng là tên một con bò của John, là một cách sắp xếp những con bò của John thỏa mãn những điều kiện trên. Nếu tồn tại nhiều cách sắp xếp thì hãy in ra cách có thứ tự từ điển bé nhất.
Sample Input
3
Buttercup must be milked beside Bella
Blue must be milked beside Bella
Sue must be milked beside Beatrice
Sample Output
Beatrice
Sue
Belinda
Bessie
Betsy
Blue
Bella
Buttercup
Comments