You are testing a robot which can only walk in one direction (north), and will test the robot in a field that is marked in a grid at each meter. The robot will be placed at one of the grid marks and head north until it reaches the edge of the field. For some pairs of points, there is an underground shortcut (tunnel) between the two points. If the robot steps on either end of the shortcut, the robot goes through the shortcut and continues walking north from the other end of the shortcut.

Given the dimensions of the field and a list of S shortcuts (specified by the (x, y) coordinates of both endpoints of the shortcut), a question is whether there is a starting point for the robot that would result in it walking in an infinite loop. The following are examples of maps that could result in an infinite loop. On map1, if the robot starts in the lower left corner it will take the shortcut through a and exit through the top of the field (not an infinite loop). However, if the robot is placed in the spot in between the a shortcuts, the robot would enter an infinite loop. map2 demonstrates that an infinite loop could exist which involves going through a sequence of shortcuts before repeating (by starting in between the a and b points in the first column).

map1          map2
a..b          b..a
....          ....
a..b          a..b
....          ....

You will be given the dimensions of the field and locations for endpoints of the shortcuts, but without knowing where each shortcut goes. For example, you might be given the following.

map3
.2..
1...
...4
.3..
Your task is to determine how many different ways to connect the shortcut points would result in a potential infinite loop. For map3, the only pairing which would result in a possible infinite loop is: (2-3), (1-4).

Solution filename: shortcuts.* (c, py, java, etc.)
Input format: integers width, height the dimensions of the field on a single line, integer S the number of shortcut holes on its own line, S lines of coordinates x y for the coordinate of a shortcut hole (with the lower left corner being position 0 0). map3 would be presented as
4 4
4
0 2
1 3
1 0
3 1
Output format: number of different complete pairings of shortcuts that could result in an infinite loop.
Partial credit: Given the input as stated and a complete pairing of the shortcut holes, determine if the given pairing could result in an infinite loop.