题目描述

FJ 的农场是一个 $N \times N$ 的方形网格，由 $N \times N$ 个田地组成（$2 \le N \le 100$）。某些相邻的田地（例如，南北方向或东西方向）之间被道路隔开，而一道高高的围栏环绕着整个网格的外部边界，阻止奶牛离开农场。奶牛可以从任意一个田地自由地移动到任何一个相邻的田地（北、东、南或西），尽管除非绝对必要，它们不喜欢穿越马路。

FJ 的农场里有 $K$ 头奶牛（$1 \le K \le 100, K \le N^2$），每头奶牛都位于一个不同的田地。如果一对奶牛为了互相拜访，必须至少穿越一条马路，那么这对奶牛被认为是“遥远的”。请帮助 FJ 计算“遥远的”奶牛对的数量。

输入格式

第一行包含三个整数 $N, K$ 和 $R$。

接下来的 $R$ 行描述了 $R$ 条道路，这些道路存在于相邻的田地之间。每行包含四个整数 $r, c, r', c'$（$1 \le r, c, r', c' \le N$），表示在田地 $(r, c)$ 和相邻田地 $(r', c')$ 之间有一条道路。

最后 $K$ 行表示 $K$ 头奶牛的位置，每行包含两个整数 $r, c$。

输出格式

输出一个整数，即“遥远的”奶牛对的数量。

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

2

数据规模与约定

对于所有测试数据：

$2 \le N \le 100$，

$1 \le K \le 100, K \le N^2$，

$1 \le R \le 10000$。

$1 \le r, c, r', c' \le N$。

保证道路连接的田地 $(r, c)$ 和 $(r', c')$ 始终是相邻的，且不会重复给出相同的道路。