Livestock Lineup

题目描述

每天，农夫约翰会给他的 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$ 的前面。 请帮助农夫约翰确定一个满足所有这些约束要求的奶牛排列顺序。保证总是存在可行的排列。如果有多个排列可行，请输出按字母顺序最靠前的那个。也就是说，在所有有效排列中，第一头奶牛应当是在所有可能出现在第一位的奶牛名字里按字母序最小的；在所有以这头奶牛开头的有效排列中，第二头奶牛应当是在所有可能出现在第二位的奶牛名字里按字母序最小的；依此类推。

输入格式

第一行输入为 $N$。 接下来 $N$ 行，每行包含一句描述约束的句子，形式为“$X$ must be milked beside $Y$”，其中 $X$ 和 $Y$ 是农夫约翰的某两头奶牛的名字（8 个可能的名字如上所列）。

输出格式

请输出一组满足所有约束的奶牛挤奶顺序，共 8 行，每行输出一头奶牛的名字。 如果存在多个可行的排列，输出按字母顺序最靠前的那个。

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

提示

题目作者：Brian Dean

标签: USACO|2019|Bronze

来源

USACO|2019|Bronze