Чому корова перейшла дорогу III (Срібло)#10537
Ферма Джона є квадратною сіткою розміром n \times n, що складається з полів. Деякі пари сусідніх полів (розташованих з півночі на південь або зі заходу на схід) розділені дорогами, а вздовж усього зовнішнього периметра сітки проходить високий забір, що не дозволяє коровам залишити ферму. Корови можуть вільно переміщатися між сусідніми полями у напрямках північ, схід, південь і захід, однак вони намагаються не перетинати дороги без крайньої необхідності.
На фермі Фермера Джона перебуває корів, кожна з яких розташована на окремому полі. Пара корів називається «віддаленою», якщо для того, щоб одна корова могла дістатися до іншої, необхідно перетнути принаймні одну дорогу. Допоможіть Фермеру Джону підрахувати кількість віддалених пар корів.
У першому рядку містяться три цілих числа та r~(2 \le n \le 100, 1 \le k \le 100, k \le n^2). У наступних рядках описано дороги, що розділяють пари сусідніх полів. Кожен рядок має вигляд r~c~r'~c' (цілі числа в діапазоні ), що позначає наявність дороги між полем у рядку , стовпці та сусіднім з ним полем у рядку r', стовпці c'. В останніх рядках вказано розташування корів — для кожної корови задано номер рядка та номер стовпця її поля.
Виведіть кількість пар корів, що є «віддаленими».
Приклад 1