407406: GYM102785 B Gremlins attack!

There's an emergency in a county-level American town. Gremlins have scattered around the town and thus the rest of the world is in danger, as, at least, one of them seems to have left the town. Special intelligence services are currently restoring the course of events and trying to identify the earliest moment when it could happen.

The town is represented in the form of a square checkered board of size $$$N\times N$$$. Each cell represents a single house. Gremlins are, typically, afraid of bright light and therefore tend to hide in darkness. Furthermore, as people go to bed, the lights in the houses are going out. Gremlins can move horizontally and vertically from one house, where the light is off, to another. As soon as they reach the house which is on the border of the town, they escape from the town.

You have reliable data about which houses gremlins occupied in the beginning, as well as the history of turning the lights off in the houses. You need to display number of the house in history, from which after turning the light off, at least, one gremlin could escape from the town. If gremlins can escape from the town immediately, type 0. The numbering of houses in history starts with one.

In the first line, three integers are entered, separated by spaces, $$$1<N<=500$$$, $$$1<=M<=N^2$$$, $$$1<=K<=N^2$$$, where $$$N$$$ determines the size of the city, $$$M$$$ is the number of houses in which gremlins are located at the beginning, $$$K$$$ is the size of the history of turning off lights in the houses.

Then there are $$$M$$$ lines, each of which contains a pair of numbers $$$0<=x_i,y_i<N$$$, specifying the coordinates of the houses where gremlins are located at the beginning. After that, there follow $$$K$$$ lines, each of which contains a pair of numbers $$$0<=x_j,y_j<N$$$, specifying the coordinates of the houses in which the light is turned off.

The single number from $$$0$$$ to $$$K$$$, which sets the number of the house, in which after turning off the light, at least, one gremlin had the opportunity to escape from the town.

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

The input data guarantee that the escape could have been made.