Команда Москвы на Всероссийской олимпиаде по информатике 2017 года оказалась настолько велика, что помещается только в 2 вагона. Некоторые школьники испытывают друг к другу такую личную неприязнь, что не могут есть, находясь в одном вагоне. Поскольку не есть в поезде нельзя (это противоречит СанПиНам), то участников олимпиады надо рассадить так, чтобы школьники, испытывающие взаимную неприязнь, ехали в разных вагонах. Если это невозможно, никто никуда не поедет.
Первая строка входного файла содержит количество школьников N (1 ≤ N ≤ 10000) и количество взаимных неприязней M (1 ≤ M ≤ 100000). Следующие M строк содержат пары чисел, задающих номера участников, испытывающих взаимную неприязнь. Участники нумеруются с единицы.
В случае, если рассадить участников невозможно — выведите единственное число 0. Если же рассадка возможна, выведите в первой строке номера школьников, едущих в первом вагоне, во второй — едущих во втором вагоне. Первый школьник всегда должен ехать в первом вагоне. Школьник с меньшим номером должен находится в первом вагоне, если это возможно. Номера школьников в каждом из вагонов должны быть упорядочены по возрастанию.
4 3 1 2 2 3 2 4
1 3 4 2
Кладоискателю Васе попалась карта древнего подземелья. Подземелье представляет собой лабиринт размера \(N \times M\) (\(1 \le N, M \le 100\), \(N \times M \le 100\)). Каждая клетка лабиринта либо пуста и по ней можно пройти, либо содержит стену. Из клетки можно переходить только в смежную по стене клетку (так, у каждой клетки может быть не более 4 смежных).
В одной из клеток находится клад, который и хочет достать Вася. В лабиринте есть \(K\) входов, из которых Вася может начать свой путь.
Требуется определить, с какого входа Васе нужно начать свой путь, чтобы пройденное расстояние до клада было наименьшим. Если таких входов несколько, нужно вывести вход с наименьшим номером.
Первая строка содержит 2 числа \(N\) и \(M\), задающие размеры лабиринта. Далее следует описание лабиринта: \(N\) строк по \(M\) символов в каждой. 0 означает, что клетка свободна; 1, что в клетке находится стена. Символ * обозначает клетку с сокровищем (такая клетка в лабиринте ровно одна).
В \((N+2)\)-й строке находится число \(K\) (\(1 \le K \le N \times M\)) -- количество входов в лабиринт. Далее в \(K\) строках содержатся координаты входов. Так, в \(i\)-й строке содержатся числа \(x_i\) и \(y_i\), означающие,что \(i\)-й вход расположен в \(x_i\)-й строке и в \(y_i\)-м столбце (\(1 \le x_i \le N, 1 \le y_i \le M\)). Гарантируется, что координаты входов попарно различны, и то, что все входы расположены в пустых клетках. Ни один из входов не находится в клетке с сокровищем.
Необходимо вывести одно число - искомый номер входа (нумерация начинается с 1). Если до сокровища невозможно добраться, выведите -1.
5 5 00000 00000 10*00 01111 00000 4 1 1 1 5 4 1 5 5
1
3 3 010 1*1 010 4 1 1 1 3 3 1 3 3
-1
Вася из задачи A по-прежнему занят поиском кладов. Более того, у него появились последователи. Один из таких последователей попросил Васю помочь в своих поисках. Так, по карте сокровищ Васю просят восстановить кратчайший путь до клада. Конфигурация лабиринта совпадает с конфигурацией, описанной в задаче A (поле \(N \times M\) (\(1 \le N, M \le 100\), \(N \times M \le 100\))), в одной клетке которого находится клад, в \(K\) клетках находятся входы в лабиринт).
Требуется вывести искомый путь.
Первая строка содержит 2 числа \(N <= 100\) и \(M <= 100\), задающие размеры лабиринта. Далее следует описание лабиринта: \(N\) строк по \(M\) символов в каждой. 0 означает, что клетка свободна; 1, что в клетке находится стена. Символ * обозначает клетку с сокровищем (такая клетка в лабиринте ровно одна).
В \((N+2)\)-й строке находится число \(K\) (\(1 \le K \le N \times M\)) -- количество входов в лабиринт. Далее в \(K\) строках содержатся координаты входов. Так, в \(i\)-й строке содержатся числа \(x_i\) и \(y_i\), означающие,что \(i\)-й вход расположен в \(x_i\)-й строке и в \(y_i\)-м столбце (\(1 \le x_i \le N, 1 \le y_i \le M\)). Гарантируется, что координаты входов попарно различны, и то, что все входы расположены в пустых клетках. Ни один из входов не находится в клетке с сокровищем.
В первой строке вывести одно число - длину кратчайшего маршрута. В следующих строках необходимо вывести кратчайший маршрут. Каждую клетку маршрута (включая начальную и конечную) вывести на отдельной строке в формате \(x_i\) \(y_i\), где \(x_i\) - строка клетки, а \(y_i\) - столбец клетки.
Если существует несколько путей минимальной длины, выведите любой. Если до сокровища невозможно добраться, в единственной строке выведите -1.
5 5 00000 00000 10*00 01111 00000 4 1 1 1 5 4 1 5 5
4
3 3 010 1*1 010 4 1 1 1 3 3 1 3 3
-1
Невзвешенный ориентированный граф задан своей матрицей смежности. Требуется построить его транзитивное замыкание, то есть матрицу, в которой в \(i\)-й строке и \(j\)-м столбце находится 1, если от вершины \(i\) можно добраться до вершины \(j\), и 0 - иначе.
В первой строке дано число \(N\) (\(1 \le N \le 100\)) - число вершин в графе. Далее задана матрица смежности графа: в \(N\) строках даны по \(N\) чисел 0 или 1 в каждой. \(i\)-е число в \(i\)-й строке всегда равно 1.
Необходимо вывести матрицу транзитивного замыкания графа в формате, аналогичным формату матрицы смежности.
4 1 1 0 0 0 1 1 0 1 0 1 0 0 0 1 1
1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1