Каждый день Фермер Джон доит своих 8 коров, которых зовут
Bessie, Buttercup, Belinda, Beatrice, Bella, Blue, Betsy, и Sue.
К несчастью, коровы довольно разборчивы и требуют, чтобы ФД доил их
в порядке, который соответствует \(N\) ограничениям (\(1 \leq N \leq 7\)).
Каждое из ограничений имеет вид "\(X\) must be milked beside \(Y\)"
("\(X\) необходимо подоить рядом \(Y\)"), что означает, что в порядке дойки
корову \(X\) нужно доить сразу после коровы \(Y\) или непосредственно перед
коровой \(Y\).
Пожалуйста, помогите ФД определить порядок дойки его коров, который
удовлетворяет всем требуемым ограничениям. Гарантируется, что такое
упорядочивание всегда возможно. Если возможно несколько упорядочиваний,
выведите первое из них в алфавитном порядке. То есть, первая корова должна иметь
наименьшее в алфавитном порядке имя из всех возможных имён, которые могут быть
первыми. Среди всех упорядочиваний, начинающихся с этой же первой коровы,
вторая корова должна быть наименьшей в алфавитном порядке среди всех
корректных упорядочиваний и т.д.
ФОРМАТ ВВОДА (файл lineup.in):
Первая строка ввода содержит \(N\). Каждая из последующих \(N\) строк
содержит предложение описывающее ограничение вида
"\(X\) must be milked beside \(Y\)"
где \(X\) и \(Y\) - имена некоторых их коров ФД
(8 возможных вариантов перечислены в начале условия задачи).
ФОРМАТ ВЫВОДА (файл lineup.out):
Выведите, используя 8 строк, порядок имён коров, по одному в строке,
удовлетворяющий всем ограничениям. Если возможно несколько порядков,
выведите наиболее ранний в смысле алфавита.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|