Why Did the Cow Cross the Road III (Silver)#10537
FJ's farm is arranged as an n \times n square grid of fields. Certain pairs of adjacent fields (north-south or east-west) are separated by roads, and a tall fence runs along the entire outer perimeter of the grid, preventing cows from leaving the farm. Cows can move freely between adjacent fields in the north, east, south, or west directions, although they prefer not to cross roads unless absolutely necessary.
There are cows on FJ's farm, each located in a different field. A pair of cows is called "distant" if, in order for one cow to visit the other, it is necessary to cross at least one road. Help FJ count the number of distant pairs of cows.
The first line contains three integers , and r~(2 \le n \le 100, 1 \le k \le 100, k \le n^2). The next lines describe the roads separating pairs of adjacent fields. Each line has the form r~c~r'~c' (integers in the range ), indicating a road between the field in row , column , and the adjacent field in row r', column c'. The final lines specify the locations of the cows, each given by its row and column.
Print the number of pairs of cows that are distant.
Beispiel 1