Сегодня вам предстоит решить задачу, с которой не может справиться сам Эркюль Пуаро! Именно поэтому данное преступление до сих пор не раскрыто, и эта история так и не вошла в детективы Агаты Кристи.
Вам не сообщается, какое совершено преступление, где и когда обнаружен труп и остальные детали. Известно только то, что преступление совершено в доме, имеющем n комнат и m дверей между парами комнат. Жильцы дома очень подозрительны, поэтому все двери запираются на ключ и все ключи различны. Согласно показаниям свидетелей в ночь с четверга на пятницу все двери в доме были заперты и известно, в каких комнатах находились жильцы и какие ключи у кого были. Аналогичная информация известна и про ночь с пятницы на субботу, в которую все двери также были заперты. В пятницу лил сильный дождь, поэтому из дома никто не выходил и никто в него не входил. В течение дня обитатели дома могли
«Серые клеточки» Эркюля Пуаро не способны справиться с таким количеством информации. Определите, могло ли из расположения людей и ключей в первую ночь получиться расположение во вторую ночь, или кто-то из свидетелей точно лжет.
В первой строке заданы три числа n, m и k (1 ≤ n, m, k ≤ 1000) — количество комнат, количество дверей и количество жильцов в доме соответственно. Следующие m строк содержат пары номеров комнат, которые соединяют двери. Комнаты нумеруются целыми числами от 1 до n. Между парой комнат может быть более одной двери. Никакая дверь не соединяет комнату саму с собой. Следующие k строк описывают расположение жильцов в первую ночь. В каждой строке содержится имя жильца (непустая строка из не более 10 латинских букв), через пробел следует номер комнаты, затем через пробел — количество имеющихся у жильца ключей. Далее через пробел перечислены номера дверей, которые открываются имеющимися ключами. Двери нумеруются целыми числами от 1 до m в порядке их описания во входных данных. Все имена жильцов различны, строчные и заглавные буквы различаются. Каждый из m ключей встречается в описании ровно один раз. Несколько людей могут находиться в одной комнате, некоторые комнаты могут быть пусты. Следующие k строк описывают расположение жильцов во вторую ночь точно в таком же формате. Гарантируется, что в описании второй ночи имена жильцов те же самые и каждый из m ключей встречается ровно один раз.
Выведите «YES» (без кавычек), если из первого расположения можно получить второе, и «NO» в противном случае.
2 1 2
1 2
Dmitry 1 1 1
Natalia 2 0
Natalia 1 1 1
Dmitry 2 0
YES
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
NO
| Школьная индивидуальная олимпиада #2 (ЗКШ 2010/11) - Codeforces Beta Round 43 (ACM-ICPC Rules) |
|---|
| Закончено |
