Tại sao con bò băng qua đường? Một lý do là trang trại của Farmer John có quá nhiều đường, khiến đàn bò của ông không thể đi lại mà không phải băng qua nhiều con đường.

Trang trại của FJ được bố trí thành một lưới ô vuông \(N \times N\) gồm các cánh đồng (\(2 \leq N \leq 100\)). Một số cặp cánh đồng kề nhau (theo hướng bắc-nam hoặc đông-tây) bị ngăn cách bởi đường, và một hàng rào cao chạy quanh toàn bộ chu vi bên ngoài của lưới, ngăn bò rời khỏi trang trại. Bò có thể tự do di chuyển từ bất kỳ cánh đồng nào sang một cánh đồng kề nó (về phía bắc, đông, nam hoặc tây), mặc dù chúng không muốn băng qua đường trừ khi thực sự cần thiết.

Có \(K\) con bò (\(1 \leq K \leq 100, K \leq N^2\)) trong trang trại của FJ, mỗi con ở một cánh đồng khác nhau. Một cặp bò được gọi là "xa cách" nếu một con bắt buộc phải băng qua ít nhất một con đường để đến thăm con còn lại. Hãy giúp FJ đếm số cặp bò xa cách.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), \(K\) và \(R\). \(R\) dòng tiếp theo mô tả \(R\) con đường nằm giữa các cặp cánh đồng kề nhau. Mỗi dòng có dạng \(r\) \(c\) \(r'\) \(c'\) (các số nguyên trong khoảng \(1 \ldots N\)), biểu thị một con đường nằm giữa cánh đồng ở (hàng \(r\), cột \(c\)) và cánh đồng kề nó ở (hàng \(r'\), cột \(c'\)). \(K\) dòng cuối cùng cho biết vị trí của \(K\) con bò, mỗi vị trí được xác định bằng một hàng và một cột.

Dữ liệu ra

In ra số cặp bò xa cách.

Ví dụ

3 3 3
2 2 2 3
3 3 3 2
3 3 2 3
3 3
2 2
2 3

2

Nguồn

USACO 2017 February Contest, Silver — Why Did the Cow Cross the Road III. Tác giả đề: Brian Dean.

https://usaco.org/index.php?page=viewproblem2&cpid=716