\textit{Что же вы так убиваетесь? Вы же так никогда не убьётесь!} \textit{Фольклор} Девочка Даша хочет решить шахматную головоломку. На доску размера \textbf{n}×\textbf{n} необходимо поставить минимальное количество ферзей так, чтобы они били все поля доски. Головоломка осложняется тем, что на некоторые поля доски ставить ферзей запрещено. Ферзь, это шахматная фигура, которая ходит по диагонали, вертикали или горизонтали на расстояние, ограниченное лишь размерами доски. Ферзь во время своего хода не может перескакивать через другого ферзя. Ферзь бьёт поле, на котором он стоит, а также все поля, на которые он может пойти. Помогите Даше написать программу, решающую головоломку. \InputFile В первой строке входного файла заданы через пробел два целых числа \textbf{n} и \textbf{k} - размер доски и количество запрещенных полей (\textbf{3} ≤ \textbf{n} ≤ \textbf{10}, \textbf{0} ≤ \textbf{k} ≤ \textbf{n^2}). В следующих \textbf{k} строках заданы координаты запрещенных полей. Координаты поля задаются через пробел двумя целыми числами \textbf{r} и \textbf{c} (\textbf{1} ≤ \textbf{r}, \textbf{c} ≤ \textbf{n}). Гарантируется, что все запрещённые поля попарно различны. \OutputFile В первой строке выходного файла выведите \textbf{m} - минимальное количество ферзей. В следующих \textbf{m} строках выведите координаты полей, на которые поставлены ферзи. Если решений несколько, выведите любое из них. Если решения не существует, выходной файл должен содержать единственное число \textbf{-1}.