Петя с Васей решили поздравить всех своих одноклассниц с Международным Женским Днем. Важной частью любого праздника являются открытки. Купив их достаточно, друзья сели писать пожелания. Подписанные открытки они складывали на специальный стол, расчерченный в квадратную клетку параллельно краям стола так, что длина и ширина его составляли N и M клеток соответственно. По удивительному совпадению каждая открытка была размером точь-в-точь с две клетки стола. Петя настоял на том, чтобы класть подписанные поздравления строго по линиям сетки — горизонтально или вертикально, накрывая одной открыткой ровно две клетки.
По окончанию работы оказалось, что каждая клетка стола накрыта ровно двумя открытками — крайне неудобное расположение для того, чтобы их дарить. К счастью, рядом был еще один такой же стол, поэтому они решили переложить на него половину открыток так, чтобы остальные, оставаясь на своем месте, образовывали ровно один слой — не накладывались друг на друга и полностью покрывали бы стол. Чтобы не нарушать порядка, открытки надо доставать по одной, извлекать очередную разрешается только в случае, если хотя бы одна из ее половинок лежит сверху (то есть эту половинку не накрывает другая открытка).
Поскольку одноклассниц у Пети и Васи довольно много, они обратились за помощью к Вам. Напишите программу, которая подскажет, какие открытки извлекать и в какой последовательности, либо определит, что это невозможно.
В первой строке входного файла записаны два целых числа N и M (1 ≤ N, M ≤ 700) — длина и ширина стола. Гарантируется, что хотя бы одно из N, M четное. Будем считать, что все открытки занумерованы числами от 1 до NM. Следующие 2N строк содержат по M чисел: первые N строк описывают нижний слой, следующие N строк — верхний слой. Число k в i-й строке j-м столбце нижнего или верхнего слоя означает наличие на этой позиции одной из половинок открытки номер k.
Гарантируется, что входные данные корректны, то есть что каждое число 1 до NM встречается ровно два раза, и эти вхождения находятся на соседних позициях, при этом они могут находиться как в одном слое, так и в разных. Кроме того, если две открытки покрывают одни и те же клетки, то одна из них находится обеими половинками снизу, а другая — сверху.
В выходной файл запишите единственное слово NO, если не существует способа извлечь половину открыток нужным образом. В противном случае в первую строку выведите YES, во вторую — последовательность из NM/2 номеров открыток, которые надо достать, в правильном порядке. У каждой из них на момент извлечения хотя бы одна из половинок должна находиться сверху. Если искомых последовательностей несколько, выведите любую из них.
Частичные ограничения
Первая группа состоит из тестов, в которых произведение NM ≤ 24.
Вторая группа состоит из тестов, в которых N, M ≤ 100.
2 2 1 1 3 2 4 2 4 3
YES 4 2
2 3 1 1 4 2 3 4 2 6 5 3 6 5
YES 2 6 5
Набор домино состоит из прямоугольных костяшек, каждая из которых разделена на две половинки линией, параллельной более короткой стороне. На каждой из половинок нарисованы точки, количество которых соответствует числу от 0 до \(M\) включительно. На костяшках полного набора домино обозначены все возможные различные пары чисел, например, если M равно 3, то полный набор содержит 10 костяшек: (0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3).
Из костяшек можно выкладывать цепочки, соединяя пары костяшек короткими сторонами, если количества точек на соседних с местом соединения половинках костяшек равны.
Некоторые костяшки были удалены из полного набора. Требуется определить, какое минимальное количество цепочек нужно выложить из оставшихся в наборе костяшек, чтобы каждая из них принадлежала ровно одной цепочке.
Напишите программу, которая по информации о наборе домино должна ответить, какое минимальное количество цепочек нужно выложить.
В первой строке входного файла содержится одно целое число \(M\) (0≤\(M\)≤100), которое соответствует максимально возможному количеству точек на половинке костяшки. Во второй строке записано одно целое число \(N\), равное количеству костяшек, удаленных из полного набора. Каждая \(і\)-я из последующих \(N\) строк содержит по два числа \(A_i\) и \(B_і\). Это количества точек на половинках \(i\)-й удалённой костяшки.
Единственная строка выходного файла должна содержать одно целое число \(L\) – минимальное количество цепочек.
7 2 7 5 3 4
2
Некогда гордая и свободолюбивая республика Акадия совсем погрязла в коррупции. Депутаты покупают и перепродают голоса друг друга, чтобы затем принять или отклонить какие-то законы. К принятым законам довольно быстро появляются поправки, их аннулирующие. Эти поправки, в свою очередь, аннулируются следующими поправками, и так далее. Секретарь премьер-министра хочет разобраться, какие законы в данный момент действуют, а какие нет.
С незапамятных времён в Акадии всего два типа законов:
* прямой закон, устанавливающий новые правовые нормы;
* поправка, аннулирующая какой-то из предыдущих законов.
Закон считается действующим тогда и только тогда, когда нет действующего закона, который бы являлся поправкой, его аннулирующей.
В распоряжении секретаря — все законы Акадии с момента становления республики в порядке их принятия. Помогите ему выяснить, какие из законов — действующие.
В первой строке ввода записано \(n\) (1 \(\le\) \(n\) \(\le\) 100000) — количество принятых законов.
Следующие \(n\) строк описывают сами законы. Каждое описание имеет следующий вид:
* «declare», если данный закон — это прямой закон.
* «cancel i», если данный закон — это поправка, аннулирующая закон с номером \(i\).
Законы нумеруются, начиная с единицы.
В первой строке вывода выведите одно число — количество действующих законов. Далее выведите номера всех действующих законов в порядке возрастания.
5 declare cancel 1 declare cancel 2 cancel 3
3 1 4 5
Тестирование и контроль качества являются чрезвычайно трудоемкими этапами разработки ПО. Для облегчения этой задачи используются несколько различных техник. Одна из них называется верификацией. Model checking — верификация на базе модели Крипке.
Модель Крипке представляет собой набор \((P, S, R, L)\), где \(P\) – конечное множество высказываний, \(S\) — конечное множество состояний модели, \(R \in SxS\) – переход из одного состояния в другое. \(L \in SхP\) – отношение истинности (высказывание \(P\) в состоянии \(S\) истинно).
Отношение \(R\) будем считать рефлексивным, т.е. \(R(S, S)\) всегда существует.
Набор состояний π, начинающийся в состоянии s, представляет собой бесконечную последовательность состояний \(s_0, s_1,...,\) такую что \(s_0 = s\) и для любого \(i ≥ 0\) выполнено \((s_i s_{i+1})\) представляет собой переход.
В данной модели существует кванторы, применяемые к наборам и к состояниям, с помощью которых образуются формулы (элементарная формула, это высказывание, оно выполняется во всех своих истинных состояниях).
Проверить формулу \(f\) – означает найти все состояния, для которых она выполняется. Для произвольной формулы это сделать сложно. Ваша задача проще – проверить формулу E(xU(AGy)), где \(x\) и \(y\) - высказывания.
Первая строка содержит три натуральных числа \(n, m\) и \(k (1 ≤ n ≤ 10 000; 0 ≤ m ≤ 100 000; 1 ≤ k ≤ 26)\) – число состояний, переходов и высказываний. Каждая из следующих \(n\) строк описывает одно из состояний. Состояние \(i (1 ≤ i ≤ n)\) описывается числом \(c_i (0 ≤ c_i ≤ k)\) – количеством высказываний, которые истинны в этом состоянии, затем через пробел перечислены эти высказывания. Сами высказывания обозначаются первыми \(k\) маленькими латинскими буквами.
Следующие \(m\) строк описывают переходы. Каждое описание содержит два числа \(s\) и \(t\)
\((1 ≤ s, t ≤ n; s ≠ t)\) – переход из состояния \(s\) в состояние \(t\). Переходы из \(s\) в \(s\) существуют всегда и во входных данных не отражены. Никакие переходы не упомянуты дважды.
Последняя строка входных данных содержит формулу, которую надо проверить. Она всегда имеет вид E(xU(AGy)), где \(x\) и \(y\) – некоторые высказывания.
Первая строка выходных данных должна содержать число состояний, для которых формула верна. Следующие строки должны содержать номера этих состояний в возрастающем порядке.
7 8 2 1 a 1 a 2 a b 1 b 1 b 1 a 1 a 1 2 2 3 3 4 4 5 5 3 2 6 6 7 7 6 E(aU(AGb))
5 1 2 3 4 5
В Тридесятом государстве есть N городов, все города пронумерованы числами от 1 до \(N\). Между городами построены дороги — каждая дорога соединяет между собой два города.
Царь Тридесятого государства уволил министра транспорта за то, что дороги были в очень плохом состоянии. Новый министр транспорта, чтобы не повторить судьбу своего предшественника, решил, что он будет лично контролировать состояние дорог. А именно он решил, что раз в год он лично будет объезжать все дороги.
При этом министр транспорта очень ценит свое время, и считает, что если в процессе объезда ему придется дважды проехать по какой-то дороге, то когда он будет ехать по этой дороге второй раз, ему уже не придется проверять ее состояние, и это будет недопустимой тратой времени.
Министр транспорта живет в городе номер 1, и поэтому хочет, чтобы его путешествие начиналось в этом городе. Заканчиваться путешествие должно в городе номер K, где каждый год будет проходить всегосударственное совещание по вопросам планирования ремонта дорог на следующий год.
Определите, какое минимальное количество дорог нужно построить в Тридесятом царстве в дополнение к уже существующим, чтобы можно было выполнить все требования Министра транспорта, а именно, чтобы он мог, выехав из города номер 1, проехать по каждой дороге ровно 1 раз и в итоге приехать в город номер \(K\).
Вводится число \(N\) — количество городов в Тридесятом царстве (1≤\(N\)≤100). Далее вводится число \(M\) — количество дорог в Тридесятом царстве (1≤\(M\)≤10000). Далее идет \(M\) пар чисел — каждая пара задает номера городов, соединяемых соответствующей дорогой. Все дороги двухсторонние, т.е. по дороге можно ездить в любую сторону. Между некоторыми городами может быть несколько дорог. Возможны дороги из города в него же. В последней строке входных данных находится число \(K\) — номер города, где заканчивается маршрут министра (1≤\(K\)≤\(N\)).
Выведите минимальное количество дорог, которое необходимо построить в Тридесятом царстве. Затем выведите, какие именно дороги надо построить: для каждой дороги выведите, какие города она должна соединять.
4 2 2 3 3 4 1
2 1 2 4 1
6 5 1 2 2 3 3 4 4 2 6 6 1
2 1 6 2 6
2 4 1 2 1 2 1 1 1 2 2
0