eolymp
bolt
Try our new interface for solving problems
Məsələlər

Шахматы

Шахматы

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Петя и Вася играют в следующую игру. Сначала Вася расставляет на шахматной доске размера n×m слонов произвольным образом. После этого Петя должен расставить на свободные клетки ладей так, чтобы, во-первых, никакие две ладьи не били друг друга, и, во-вторых, никакая ладья не стояла под боем слона.

Петя хочет расставить максимально возможное количество ладьей. Помогите ему.

Giriş verilənləri

В первой строке находятся два числа n и m (1n, m100) - количество строк и столбцов соответственно. Во второй строке находится одно число k (0kn·m) - количество слонов. В следующих k строках заданы местоположения слонов - номер строки и столбца соответственно.

Çıxış verilənləri

В первой строке выведите максимальное количество ладьей, которое может расставить Петя. В следующих строчках выведите описания положения ладей в том же формате, что и во входном файле.

Nümunə

Giriş verilənləri #1
2 2
1
2 2
Çıxış verilənləri #1
2
2 1
1 2