← 返回题目列表

Codeforces · 46/F

F. 赫尔克里波洛问题

中文机器翻译题面 查看原题

今天你要解决的问题连大名鼎鼎的赫尔克里·波洛都无法应对!这就是为什么这起犯罪事件至今尚未侦破,这个故事也从未被收录在阿加莎·克里斯蒂的侦探故事书中。

您不会被告知犯了什么罪、尸体被发现的时间和地点以及其他细节。我们只知道犯罪发生在一间有 n 个房间、每对房间之间有 m 个门的房子里。房子里的住户非常怀疑,这就是为什么所有的门都可以用钥匙锁上,而且所有的钥匙都不一样。根据周四晚上提供的证据,房子里所有的门都锁着,并且知道居民在哪些房间,以及其中任何一把钥匙是什么类型的。周五晚上也是如此,当时所有的门也都锁着。周五下着大雨,所以没有人离开房子,也没有人进屋。白天,住户可以

- 使用可用的钥匙打开和关闭相邻房间的门(每扇门都可以从每一侧打开和关闭);
- 如果相应的门打开,则可以自由地从一个房间移动到另一个房间;
- 在一个房间里互相给予钥匙。

赫尔克里·波洛的“小灰质”无法处理如此大量的信息。查明周四晚上人员和钥匙的位置是否会导致周五晚上的位置,否则证人中肯定有人在撒谎。

输入

第一行包含三个预设整数 n, m и k (1 ≤ n, m, k ≤ 1000)——分别是房间数、门数和房屋居民数。接下来的 m 行包含连接门的房间号对。房间用 1 到 n 的整数进行编号。两间房间之间最多只有一扇门。没有门将房间与其自身连接起来。接下来的 k 线描述了居民在第一晚的位置。每行包含一个住户的姓名(由不超过 10 个拉丁字母组成的非空行),然后在一个空格后跟房间号,然后在一个空格之后是该住户拥有的钥匙数量。然后按照可以用这些钥匙打开的以空格分隔的门的书面编号进行操作。门按照输入数据中描述的顺序用 1 到 m 的整数进行编号。所有居民都有不同的名字,大小写字母被认为是不同的。每个 m 个键在描述中只出现一次。一间房间可能有多个人,有些房间可能是空的。接下来的 k 线以完全相同的格式描述了第二天晚上居民的位置。保证在第二晚的描述中,居民的姓名保持不变,并且每 m 个键只出现一次。

输出

如果第二个排列可以由第一个排列产生,则打印“YES”(不带引号),否则,打印“NO”。

示例

输入 #1

2 1 2
1 2
Dmitry 1 1 1
Natalia 2 0
Natalia 1 1 1
Dmitry 2 0

输出 #1

YES

输入 #2

4 4 3
1 3
1 2
2 3
3 4
Artem 1 1 4
Dmitry 1 1 2
Edvard 4 2 1 3
Artem 2 0
Dmitry 1 0
Edvard 4 4 1 2 3 4

输出 #2

NO