Задача №410. Метро
Женя получил письмо от Леши со словесным описанием схемы метро в его городе. Метро содержит одну кольцевую линию. Каждая из остальных линий пересекается с кольцевой не более, чем в двух местах, причем в точках пересечения организованы пересадочные станции. В одном месте кольцевую линию могут пересекать сразу несколько линий, имеющих общую пересадочную станцию.
Кроме этих пересадочных станций каждая из линий имеет не более одной пересадочной станции для перехода на другие, отличные от кольцевой, линии. На такой станции также может быть организована пересадка сразу на несколько линий.
Для каждой пересадочной станции Леша описал, какие линии на ней пересекаются, и указал порядок расположения пересадочных станций на кольцевой линии. Он утверждает, что все линии расположены на одной глубине и других пересечений, помимо пересадочных узлов, не имеют. Чтобы проверить это утверждение, Женя стал по словесному описанию рисовать схему метро, но у него не получилось.
Помогите Жене написать программу, которая будет проверять, действительно ли может существовать схема метро, соответствующая полученному описанию.
На рисунке приведена возможная схема метро, соответствующая второму примеру.
В первой строке вводится число k – количество линий метро в городе ( 1
\( le\)" width="16" height="28" align="middle" />k\( le\)" width="16" height="28" align="middle" />10). Все линии пронумерованы от 0 до k - 1, кольцевая линия имеет номер 0. Во второй строке записано число n – количество пересадочных станций. Каждая из следующих n строк описывает линии, пересекающиеся на соответствующей пересадочной станции, причем сначала следуют описания пересадочных станций, расположенных на кольцевой линии, в порядке их расположения на ней. Описание каждого узла начинается с количества пересекающихся в нем линий, затем следуют номера линий.
Выведите слово YES, если по описанию можно построить схему метро, и NO в противном случае.
4 6 2 0 1 2 0 2 2 0 3 2 0 1 2 0 2 2 0 3
NO
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