Задача В. Мечты сбудутся
Задачу добавил: DK
Успешно сдано решений: 9
Задача B. Мечты сбудутся
Ограничение по времени: 1 секунда
Ограничение по памяти: 64 МБ
Название задачи (англ.): Distant future
Был предложен проект газораспределительной станции на границе с Аниарку. Станция состояла из N узлов сети, некоторые из которых соединены между собой трубами. Для создании станции был возведен каркас, представляющий собой трёхмерную прямоугольную сетку с шагом один метр. Задача – проверить, возможно ли реализовать проект. Формальное описание условий следующее:
1. Любой узел сети должен находиться в узле сетки (т.е. в точке с целочисленными координатами). Узел сети следует считать материальной точкой.
2. Любая труба должна соединять ровно два узла сети.
3. Никакие две трубы не должны пересекаться, за исключением, возможно, одного узла сети.
4. Любая труба должна состоять из последовательности прямых участков длины 1м, каждый следующий должен стыковаться с предыдущим в узле сетки. Первый и последний участки должен стыковаться с узлами сети, которые считаются соединенными трубой.
5. Любая труба двунаправлена. Если в изначальном проекте узел сети А соединен с узлом сети В, то узел В соединен с А.
Входной файл.
В первой строке целое число N - количество узлов сети. В каждой из следующих N строк целое число Ai (1 <= i <= N) – число узлов, соединенных с i-ым узлом сети, далее через пробел номера этих узлов. Никакая пара узлов не соединены более одного раза. Никакой узел не соединен сам с собой. Если узел А соединен с В, то узел В соединен с А, причем это отражено в списке.
Выходной файл.
В единственной строке файла ответ "YES", если требования могут быть удовлетворены, и "NO" иначе.
|
Входной файл input.txt |
Выходной файл output.txt |
|
5 4 2 3 4 5 4 1 3 4 5 4 1 2 4 5 4 1 2 3 5 4 1 2 3 4 |
YES |
|
8 7 2 3 4 5 6 7 8 1 1 1 1 1 1 1 1 1 1 1 1 1 1 |
NO |
Подсказка к примеру 2:
Комментарий. Согласно разъяснению жюри (номер 1) N <= 10.