--->
2 задач
<---
Петя с Васей решили поздравить всех своих одноклассниц с Международным Женским Днем. Важной частью любого праздника являются открытки. Купив их достаточно, друзья сели писать пожелания. Подписанные открытки они складывали на специальный стол, расчерченный в квадратную клетку параллельно краям стола так, что длина и ширина его составляли 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
На отдыхе в Теплой Стране Вера познакомилась с симпатичным волейболистом- трактористом Петром. Турист Петр, кстати, собирается после отличного отдыха в Теплой Стране отправиться в путешествие по городам Европы. Как известно, Европа обладает развитой транспортной системой: в Европе есть \(V\) интересующих Петра городов и \(E\) маршрутов ночных поездов. Каждый маршрут соединяет два различных города, время в пути составляет одну ночь. Поезда по маршруту ходят в обоих направлениях.
Основной целью поездки Петра является осмотр местных достопримечательностей. По- скольку Петр — невероятно занятой человек, то он решил, что все путешествие должно занимать не более четырех дней. Петр уже многое повидал, поэтому на осмотр достопримечательностей в каждом городе Петр тратит ровно один день. Он хочет составить наиболее практичный тур: каждый день он будет тратить на осмотр города, а каждую ночь — на переезд ночным поездом между городами. Разумеется, Петр не имеет ни малейшего желания посещать один город несколько раз.
Но на этом прагматичность Петра не заканчивается: Петр, как настоящий турист, хочет посмотреть на самые красивые европейские достопримечательности. Он долго изучал справочники и для каждого города оценил свою ожидаемую радость от его посещения \(p_i\). Теперь он хочет найти маршрут, при котором его радость будет наибольшей. Помогите Петру найти такой маршрут.
В первой строке входных данных заданы два целых числа \(V\) и \(E\) (1 ≤ \(V\); \(E \le 3*10^5\)) — количество городов и маршрутов поездов, соответственно. В следующей строке заданы V целых чисел \(p_i\) (1 ≤ \(p_i\) ≤ \(10^8\)), где \(p_i\) обозначает ожидаемую радость от посещения го- рода с номером \(i\). В следующих \(E\) строках заданы описания маршрутов поездов. Каждое описание состоит из пары различных чисел \(a_i\) и \(b_i\) (1 ≤ \(a_i\); \(b_i\) ≤ V\( \)) — номеров городов, между которыми курсирует этот маршрут поезда. Гарантируется, что между каждой парой городов существует не более одного маршрута поезда.
В первой строке выходных данных выведите число K (1 ≤ K ≤ 4) — количество городов в оптимальном маршруте туриста Петра. В следующей строке выведите номера этих городов в порядке посещения. Города нумеруются начиная с единицы. Если оптимальных маршрутов несколько, выведите любой из них.
Тесты к этой задаче состоят из пяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.
0. Тесты 1–2. Тесты из условия, оцениваются в ноль баллов.
1. Тесты 3–16. В тестах этой группы \(V\); \(E\) ≤ 100. Эта группа оценивается в 20 баллов
2. Тесты 17–32. В тестах этой группы \(V\); \(E\) ≤ 1 000. Эта группа оценивается в 20 баллов.
3. Тесты 33–53. В тестах этой группы \(V\) ≤ 3 000, \(E\) ≤ 60 000. Эта группа оценивается в 30 баллов.
4. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 30 баллов. Решение будет тестироваться на тестах этой группы offline, т. е. после окончания тура.
5 4 4 2 3 1 5 1 2 2 3 3 4 4 5
4 2 3 4 5
4 3 1 2 3 4 1 2 1 3 1 4
3 4 1 3