아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Метро

시간 제한2초메모리 제한1024 MB

요약
어떤 노선들이 만나는지 나열한 환승역 목록이 주어질 때, 하나의 순환선과 순환선을 최대 두 번 지나는 노선들로 구성된 지하철 배치가 존재하는지 판정합니다.
난이도

보통10점 중 7점

유형
그래프, 기하, 구현
정답자
아직 제출이 없습니다

문제

Женя получил письмо от Леши со словесным описанием схемы метро в его городе. Метро содержит одну кольцевую линию. Каждая из остальных линий пересекается с кольцевой не более чем в двух местах, причем в точках пересечения организованы пересадочные станции. В одном месте кольцевую линию могут пересекать сразу несколько линий, имеющих общую пересадочную станцию. 

Кроме этих пересадочных станций каждая из линий имеет не более одной пересадочной станции для перехода на другие, отличные от кольцевой, линии. На такой станции также может быть организована пересадка сразу на несколько линий.

Для каждой пересадочной станции Леша описал, какие линии на ней пересекаются, и указал порядок расположения пересадочных станций на кольцевой линии. Он утверждает, что все линии расположены на одной глубине и других пересечений, помимо пересадочных узлов, не имеют. Чтобы проверить это утверждение, Женя стал по словесному описанию рисовать схему метро, но у него не получилось.

Помогите Жене написать программу, которая будет проверять, действительно ли может существовать схема метро, соответствующая полученному описанию.

На рисунке приведена возможная схема метро, соответствующая второму примеру.

입력

В первой строке входного файла содержится число kk --- количество линий метро в городе (1≤k≤101 \le k \le 10). Все линии пронумерованы от 0 до k−1k - 1, кольцевая линия имеет номер 0. Во второй строке записано число nn --- количество пересадочных станций. Каждая из следующих nn строк описывает линии, пересекающиеся на соответствующей пересадочной станции, причем сначала следуют описания пересадочных станций, расположенных на кольцевой линии, в порядке их расположения на ней. Описание каждого узла начинается с количества пересекающихся в нем линий, затем следуют номера линий.

출력

Выведите в выходной файл слово YES, если по описанию можно построить схему метро, и NO в противном случае.

예제2

  1. 예제 1

    입력
    4
6
2 0 1
2 0 2
2 0 3
2 0 1
2 0 2
2 0 3
    예상 출력
    NO

  2. 예제 2

    입력
    6
6
3 0 1 4
2 0 1
3 0 2 3
3 0 2 3
3 1 3 5
2 2 4
    예상 출력
    YES