CF46F Hercule Poirot Problem

今天你要解决一个连著名侦探赫尔克里·波洛都无法解决的问题！因此，这起案件至今未被侦破，这个故事也未曾被收录在阿加莎·克里斯蒂的侦探小说中。 你不知道具体发生了什么案件，也不知道尸体何时何地被发现，更不知道其他细节。我们只知道案件发生在一个有 $n$ 个房间、房间两两之间通过 $m$ 扇门相连的房子里。房子的居民们非常多疑，因此所有的门都配有钥匙，且每把钥匙都不相同。根据提供的证据，周四晚上房子的所有门都被锁上，居民们各自在某些房间，并且每个人手中的钥匙种类都已知。周五晚上也是如此，所有门再次被锁上，且每个人所在的房间以及持有的钥匙种类也都已知。周五当天大雨滂沱，没有人离开房子，也没有人进入房子。在这一天中，居民可以： - 用自己拥有的钥匙开关与邻近房间之间的门（每扇门可以从两边上锁和开锁）； - 如果有相应的门敞开，可以在房间间自由移动； - 只要在同一个房间中，可以将钥匙相互转交。 波洛的“小灰细胞”无法应付如此繁杂的信息量！请判断：周四晚的人员与钥匙分布，是否有可能在中间若干天的操作后，最终达到周五晚的分布？如果做不到，那么肯定有证人在撒谎。

第一行包含三个整数 $n$、$m$ 和 $k$（$1\leq n,m,k\leq 1000$），分别表示房间数、门数和居民人数。接下来的 $m$ 行，每行两个房间编号，表示一扇门连接的房间（房间编号从 $1$ 到 $n$，任意一对房间之间最多只有一扇门，且没有门连接同一房间）。 接下来的 $k$ 行描述第一晚居民的分布。每行依次为：居民姓名（由不超过 10 个英文字母组成，非空字符串，区分大小写），空格，房间编号，空格，居民手中的钥匙数量，之后是空格分隔的钥匙对应的门的编号（门的编号为输入顺序，从 $1$ 到 $m$）。所有居民姓名互不相同。每把钥匙只被一人持有，每个人可能有多把钥匙。多个居民可以在同一房间，某些房间可能为空。 接下来的 $k$ 行描述第二晚居民的分布，格式与第一晚完全相同，居民姓名顺序与第一次完全一致，且每把钥匙仍然唯一分配给某个人。

如果第二晚的分布可能由第一晚转化而来，输出 "YES"；否则输出 "NO"。

由 ChatGPT 5 翻译