Duchess
The Lackey-Pike pulled out an enormous letter from under his arm—almost as big as he was—and handed it to the Little Frog.
"To the Duchess," he announced with great importance. "From the Queen. An invitation to croquet."
The Little Frog took the letter and, with equal importance, repeated the words, only slightly rearranging them:
"From the Queen. To the Duchess. An invitation to croquet."
Alice's Adventures in Wonderland (translation by N.M. Demurova)
The Duchess is preparing for the royal croquet game and is sewing a special corset for the occasion. This corset features lacing holes, with a total of N+M holes arranged in 2 rows: one row contains N holes, and the other has M holes.
The lacing is quite intricate—special ties connect holes from the first row to those in the second row, resulting in numerous intersections between the rows. The Duchess is in a quandary—she must know the number of these intersections to avoid offending the Queen with her ignorance.
While the Duchess may not be the most sympathetic character—just look at the portrait of the "Ugly Duchess" by the 16th century artist Quinten Massys—she still needs assistance. It is believed that Margarete Maultasch, Duchess of Carinthia and Tyrol (14th century), inspired the first illustrations of the Duchess in "Alice's Adventures in Wonderland." Regardless, the Duchess requires help.
Let's assume the N points in the first row have coordinates (0,1), (0,2), ..., (0,N), and the M points in the second row have coordinates (1,1), (1,2), ..., (1,M). Some points with different x-coordinates are connected by segments, and it is necessary to determine how many different pairs of these segments intersect.
Input
The first line contains the numbers N, M, K, where K is the number of segments connecting the points (1 ≤ N, M ≤ 300, 1 ≤ K ≤ N*M). The next K lines each contain two numbers X and Y, indicating that a segment connects the points with coordinates (0,X) and (1,Y). All segments listed in the input are unique.
Output
Output the number of pairs of segments that intersect. Note that segments touching at their endpoints do not count as intersections.