CF46F.Hercule Poirot Problem

Today you are to solve the problem even the famous Hercule Poirot can't cope with! That's why this crime has not yet been solved and this story was never included in Agatha Christie's detective story books.

You are not informed on what crime was committed, when and where the corpse was found and other details. We only know that the crime was committed in a house that has n rooms and m doors between the pairs of rooms. The house residents are very suspicious, that's why all the doors can be locked with keys and all the keys are different. According to the provided evidence on Thursday night all the doors in the house were locked, and it is known in what rooms were the residents, and what kind of keys had any one of them. The same is known for the Friday night, when all the doors were also locked. On Friday it was raining heavily, that's why nobody left the house and nobody entered it. During the day the house residents could

• open and close doors to the neighboring rooms using the keys at their disposal (every door can be opened and closed from each side);
• move freely from a room to a room if a corresponding door is open;
• give keys to one another, being in one room.

"Little grey matter" of Hercule Poirot are not capable of coping with such amount of information. Find out if the positions of people and keys on the Thursday night could result in the positions on Friday night, otherwise somebody among the witnesses is surely lying.

今天，你将要解决一个连著名的赫尔克里·波洛（Hercule Poirot）都束手无策的问题！正因如此，这起案件至今仍未告破，这个故事也从未被收录进阿加莎·克里斯蒂（Agatha Christie）的侦探小说中。

你并未被告知究竟发生了何种罪行、尸体是在何时何地被发现，以及其他细节。我们只知道：犯罪发生于一栋拥有 $n$ 个房间和 $m$ 扇连接若干房间对的门的住宅中。屋内居民都非常可疑，因此所有门均需用钥匙上锁，且所有钥匙各不相同。根据现有证据，周四晚上，整栋住宅的所有门均处于上锁状态；同时已知每位居民当时所处的房间，以及每人手中持有的钥匙种类。同样地，周五晚上所有门也均为上锁状态，此时每位居民所处的房间及各自持有的钥匙种类亦已知。周五全天大雨滂沱，因此无人离开住宅，也无人进入住宅。而在白天，住宅居民可执行以下操作：

• 使用自己手中的钥匙开启或关闭通往相邻房间的门（每扇门均可从两侧开启或关闭）；
• 若某扇门处于开启状态，则可在相应两房间之间自由通行；
• 若两人身处同一房间，则可相互转交钥匙。

赫尔克里·波洛那“小小的灰色脑细胞”无法处理如此庞杂的信息。请判断：周四晚上的人员与钥匙分布是否可能通过合法操作演变为周五晚上的分布；若不可能，则证人中必有人在说谎。

The first line contains three preset integers n, m и k (1 ≤ n, m, k ≤ 1000) — the number of rooms, the number of doors and the number of house residents respectively. The next m lines contain pairs of room numbers which join the doors. The rooms are numbered with integers from 1 to n. There cannot be more that one door between the pair of rooms. No door connects a room with itself. The next k lines describe the residents' position on the first night. Every line contains a resident's name (a non-empty line consisting of no more than 10 Latin letters), then after a space follows the room number, then, after a space — the number of keys the resident has. Then follow written space-separated numbers of the doors that can be unlocked by these keys. The doors are numbered with integers from 1 to m in the order in which they are described in the input data. All the residents have different names, uppercase and lowercase letters considered to be different. Every m keys occurs exactly once in the description. Multiple people may be present in one room, some rooms may be empty. The next k lines describe the position of the residents on the second night in the very same format. It is guaranteed that in the second night's description the residents' names remain the same and every m keys occurs exactly once.

第一行包含三个预设整数 $n$、$m$ 和 $k$（$1 ≤ n, m, k ≤ 1000$），分别表示房间数、门数和住户数。接下来的 $m$ 行每行包含一对房间编号，表示由一扇门连接的两个房间。房间编号为从 $1$ 到 $n$ 的整数。任意两个房间之间至多只有一扇门，且不存在连接房间与其自身的门。接下来的 $k$ 行描述了第一晚各住户的位置。每行包含一个住户姓名（一个非空字符串，仅由不超过 10 个拉丁字母组成），其后是一个空格，接着是该住户所在的房间编号，再后是一个空格，然后是该住户所拥有的钥匙数量；随后是若干个用空格分隔的门编号，表示这些钥匙所能开启的门。门的编号为从 $1$ 到 $m$ 的整数，按输入中描述门的顺序依次编号。所有住户姓名互不相同，且区分大小写。每把编号为 $1$ 至 $m$ 的钥匙在全部描述中恰好出现一次。多个住户可位于同一房间，某些房间可能为空。接下来的 $k$ 行以完全相同的格式描述第二晚各住户的位置。保证第二晚描述中住户姓名保持不变，且每把编号为 $1$ 至 $m$ 的钥匙仍恰好出现一次。

Print "YES" (without quotes) if the second arrangement can result from the first one, otherwise, print "NO".

如果第二种排列可以由第一种排列得到，则输出 "YES"（不带引号），否则输出 "NO"。