B. Гремлины атакуют!
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

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

Город представлен в виде квадратной клетчатой доски размера $$$N\times N$$$. Каждая клетка представляет один дом. Гремлины боятся яркого света и поэтому прячутся в темноте. Далее, по мере того как люди ложатся спать, свет в домах гаснет. Гремлины могут перемещаться по горизонтали и по вертикали от одного дома, где не горит свет, к другому. Как только они достигают дома, который находится на границе города, они сбегают из города.

У вас есть достоверные данные о том в каких домах гремлины находились в начале, а также история выключения света в домах. Вам надо вывести порядковый номер дома в истории, после выключения света в котором хотя бы один гремлин может сбежать из города. Если гремлины сразу же могут сбежать из города, вывести 0. Нумерация домов в истории начинается с единицы.

Входные данные

В первой строке через пробел вводятся три целых числа $$$1 \lt N \lt =500$$$, $$$1 \lt =M \lt =N^2$$$, $$$1 \lt =K \lt =N^2$$$, где $$$N$$$ определяет размер города, $$$M$$$ - количество домов, в которых в самом начале находятся гремлины, $$$K$$$ - размер истории выключений света в домах.

Далее следуют $$$M$$$ строк, каждая из которых содержит пару чисел $$$0 \lt =x_i,y_i \lt N$$$, задающих координаты домов, где находятся гремлины в начале.

После этого следуют $$$K$$$ строк, каждая из которых содержит пару чисел $$$0 \lt =x_j,y_j \lt N$$$, задающих координаты домов, в которых выключается свет.

Выходные данные

Единственное число от $$$0$$$ до $$$K$$$, которое задает номер дома, после выключения света в котором хотя бы один гремлин имел возможность сбежать из города.

Примеры
Входные данные
3 1 3
1 1
0 0
0 1
0 2
Выходные данные
2
Входные данные
5 2 5
0 1
4 1
0 0
1 1
2 2
3 3
4 4
Выходные данные
0
Входные данные
4 2 3
1 1
1 2
2 0
3 1
1 3
Выходные данные
3
Входные данные
5 2 6
1 1
3 3
1 2
1 3
2 3
3 0
3 1
2 1
Выходные данные
6
Входные данные
7 6 7
1 4
1 1
2 3
3 1
4 4
5 2
0 4
2 4
3 4
1 0
2 1
5 1
5 0
Выходные данные
1
Примечание

Входные данные гарантируют, что побег мог быть совершен.