Sabotage at Gorgopotamos

On the night of November 25th to 26th, 1942, the united resistance forces of ELAS under Aris Velouchiotis and EDES under Napoleon Zervas carried out perhaps the largest sabotage operation in occupied Europe. They disrupted the supply line of the Wehrmacht by blowing up the bridge of Gorgopotamos in Fthiotida. 60 ELAS fighters took the southern end, 40 EDES fighters the northern end, 12 English saboteurs undermined the bridge, and Captain Nikiforos of ELAS with 30 men remained hidden as a reserve to intervene if needed. Captain Nikiforos expressed his displeasure at being in reserve, but he turned out to be the decisive factor for success. As soon as the signal was given, Captain Nikiforos moved through minefields and the firing fields of machine guns, recognized beforehand, in order to to reach the northern end that posed a problem. Captain Nikiforos and his fighters had to move, choosing the shortest route, only forward or right or left, with small steps and without leaving the battlefield, to arrive at the desired point in time. It was like moving on a giant chessboard full of mines!

Problem:

Develop a program in one of the IOI languages that: A) Reads from a file the dimensions of the rectangular battlefield, the number and coordinates of the mines, the starting point, and the destination point. B) Calculates the shortest route from the starting point to the destination point, which must not exceed the dimensions of the rectangle or pass over a mine. The route must include only permissible moves (down, right, left). C) Outputs a file containing the number of moves and their coordinates. If there is no possible route, only output 0.

A downward move corresponds to an increase in ~Y~, a right move corresponds to an increase in ~X~, while a left move corresponds to a decrease in ~X~.

Input Files:

The input files named sabotage.in are text files with the following structure: The first line contains two numbers (separated by a space) X, Y (1 ~<~ X, Y ~\le~ 1.000), indicating the dimensions of the battlefield. The second line contains a number Ν (1 ~\le~ Ν ~\le~ 1.000.000), giving the number of mines or visibility points of machine guns. The next ~N~ lines contain the coordinates of the above, in the form ~X_i, Y_i~ (separated by a space). The second-to-last line has the coordinates of the starting point, and the last line has the coordinates of the destination point (separated by a space).

Output Files:

The output files named sabotage.out are text files with the following structure: The first line contains the number of moves Μ (0 ~<~ Μ ~\le~ 1.000.000). The next ~M~ lines contain the coordinates of the moves, in the form ~X_i, Y_i~ (separated by a space). If there is no possible route, only output ~0~.

Observations:

1. The field is 'rectangular' (dimensions ~X~, ~Y~).
2. The input point will always be above (~X_{eisodou}~, ~1~), while the output point will always be below (~X_{exodou}~, ~Y~).
3. Permissible moves are Down (+~Y~), Right (+~X~), or Left (~-X~).
4. There may be more than one correct route. These are scored equally among themselves.
5. Routes with more moves may be found that lead to the destination without passing through a prohibited point. These solutions will be scored at least 60% and inversely proportional to the number of additional moves.
6. There is no mine at either the start or the destination.
7. The positions of all mines are known in advance.

Examples of Input-Output Files:

1ο

STDIN (sabotage.in)

5 7
15
4 1
5 1
1 2
2 2
4 2
1 3
4 3
5 3
5 5
1 6
3 6
5 6
1 7
2 7
3 7
1 1
4 7

(Two equivalent output files) STDOUT (sabotage.out)

10
1 1
2 1
3 1
3 2
3 3
3 4
4 4
4 5
4 6
4 7

STDOUT (sabotage.out)

10
1 1
2 1
3 1
3 2
3 3
3 4
3 5
4 5
4 6
4 7

2ο

STDIN (sabotage.in)

5 7
5
1 2
2 2
3 2
4 2
5 2
4 1
2 7

STDOUT (sabotage.out)

0

Constraints

Execution time: ~10~ seconds.
Maximum memory requirement: ~32~ MB.