P5833 [USACO19DEC] Livestock Lineup B

Every day, Farmer John milks his $8$ cows. Their names are Bessie, Buttercup, Belinda, Beatrice, Bella, Blue, Betsy, and Sue. Unfortunately, these cows are quite hard to deal with. They require Farmer John to milk them in an order that satisfies $N$ constraints. Each constraint is of the form "$X$ must be milked beside $Y$", meaning cow $X$ must be immediately after cow $Y$ in the milking order, or immediately before cow $Y$. Please help Farmer John find a milking order that satisfies all constraints. It is guaranteed that such an order exists. If there are multiple valid orders, output the one with the smallest lexicographical order. That is, the first cow must be the one with the smallest name in lexicographical order among all cows that can appear first in some valid milking order. Among all valid milking orders that start with this lexicographically smallest cow, the second cow must be lexicographically smallest, and so on.

The first line contains $N$. The next $N$ lines each contain a sentence describing a constraint in the format "$X$ must be milked beside $Y$", where $X$ and $Y$ are names of Farmer John's cows (from the eight possible names listed above).

Output a cow order in $8$ lines, one cow name per line, satisfying all constraints. If multiple orders satisfy the requirements, output the lexicographically smallest cow order.

$1 \leq N \leq 7$. Problem by: Brian Dean. Translated by ChatGPT 5