Чому корова перейшла дорогу III (Срібло)
На фермі Джона є квадратна решітка розміром n на n полів. Сусідні поля (північ-південь або захід-схід) розділені дорогами, а високий паркан оточує всю решітку, не дозволяючи коровам залишити ферму. Корови можуть вільно переміщатися з одного поля на сусіднє (на північ, південь, захід, схід), але вони намагаються уникати переходів через дороги, якщо це не є необхідним.
На фермі знаходиться k корів, кожна з яких займає окреме поле. Пара корів вважається "далекою", якщо для того, щоб одна корова могла дістатися до іншої, потрібно перетнути хоча б одну дорогу. Допоможіть Джону підрахувати кількість таких "далеких" пар корів.
Вхідні дані
Перша строка містить n (2 ≤ n ≤ 100), k (1 ≤ k ≤ 100, k ≤ n^2) і r. Наступні r рядків описують r доріг між парами сусідніх полів. Кожен рядок має формат r c r′ c′ (цілі числа в діапазоні 1 .. n), що вказує на наявність дороги між сусідніми полями (рядок r, стовпець c і рядок r′, стовпець c′). Останні k рядків описують розташування k корів (рядок, стовпець).
Вихідні дані
Виведіть кількість пар "далеких" корів.