Сегодня вам предстоит решить задачу, с которой не может справиться сам Эркюль Пуаро! Именно поэтому данное преступление до сих пор не раскрыто, и эта история так и не вошла в детективы Агаты Кристи.
Вам не сообщается, какое совершено преступление, где и когда обнаружен труп и остальные детали. Известно только то, что преступление совершено в доме, имеющем n комнат и m дверей между парами комнат. Жильцы дома очень подозрительны, поэтому все двери запираются на ключ и все ключи различны. Согласно показаниям свидетелей в ночь с четверга на пятницу все двери в доме были заперты и известно, в каких комнатах находились жильцы и какие ключи у кого были. Аналогичная информация известна и про ночь с пятницы на субботу, в которую все двери также были заперты. В пятницу лил сильный дождь, поэтому из дома никто не выходил и никто в него не входил. В течение дня обитатели дома могли
- открывать и закрывать двери в соседние комнаты при помощи имеющихся ключей (каждую дверь можно открывать и закрывать с любой стороны);
- свободно перемещаться между комнатами, если соответствующие двери открыты;
- передавать друг другу ключи, находясь в одной комнате.
«Серые клеточки» Эркюля Пуаро не способны справиться с таким количеством информации. Определите, могло ли из расположения людей и ключей в первую ночь получиться расположение во вторую ночь, или кто-то из свидетелей точно лжет.
Выходные данные
Выведите «YES» (без кавычек), если из первого расположения можно получить второе, и «NO» в противном случае.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 1 2
1 2
Dmitry 1 1 1
Natalia 2 0
Natalia 1 1 1
Dmitry 2 0
|
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
|
NO
|