В мире животных проходит турнир по шахматам на доске n*m! В решающем матче встречаются коала и акула, а судит этот матч слон. Коала выигрывает, поэтому акула прибегла к нечестной тактике: она запугала слона своими зубами, и он разрешил ей поставить сколько угодно слонов на поле. Теперь акула доставляет на доску слонов. Она хочет, чтобы никакие два из поставленных ею слонов не били друг друга. Также она хочет, чтобы число слонов было максимально (ведь чем больше фигур - тем лучше). Акула рассказала вам, на каких позициях находятся фигуры в данный момент (и дала вам достаточную мотивацию ей выбрать места для слонов!
Шахматный слон ходит по диагонали и не может перепрыгивать через другие фигуры. Слонов можно ставить только на пустые клетки.
Формат входных данных
В первой строке вводятся целые числа n, m и k (1 ≤ n, m, k ≤ 500) - размеры доски (доска размера n*m) и число фигур на доске.
В следующих k строках выводятся по 2 числа: xi и yi (1 ≤ xi ≤ n, 1 ≤ yi ≤ m) - координаты i-й фигуры.
Формат результата
В первой строке выведите x (0 ≤ x ≤ n*m) - максимальное число слонов, которое вы можете поставить так, чтобы они не били друг друга.
В следующих x строках выведите по 2 числа: xi и yi - координаты i-го слона, которого вы поставили. 1 ≤ ri ≤ n, 1 ≤ ci ≤ m.
Примеры
Входные данные
3 3 0
Результат работы
4
1 1
1 2
1 3
3 2
Входные данные
3 4 2
3 3
2 3
Результат работы
7
1 1
1 2
2 4
1 4
3 2
3 1
3 4
Входные данные
1 3 2
1 2
1 3
Результат работы
1
1 1
n, m, k = map(int, input().split())
l = []
ans = []
for i in range(k):
a, b = map(int, input().split())
l.append(b)
if n == 1:
for j in range(1, m + 1):
if not j in l:
ans += [1, j]
print(len(ans) // 2)
for i in range(0, len(ans), 2):
print(ans[i], ans[i + 1])
Решение на