소가 길을 건너간 이유 6

소가 길을 건너간 이유는 그냥 길이 많아서이다. 존의 농장에는 길이 너무 많아서 길을 건너지 않고서는 별로 돌아다닐 수가 없다.

존의 농장이 대대적으로 개편되었다. 이제 농장은 작은 정사각형 목초지가 $N \times N$ ($2 \le N \le 100$) 격자로 놓인 모양이다. 인접한 두 목초지 사이는 보통 자유롭게 오갈 수 있지만, 그중 일부는 길을 건너야만 오갈 수 있다. 농장 바깥은 높은 울타리로 둘러싸여 있어서 소가 농장 밖으로 나갈 일은 없다.

존의 농장에는 소 $K$마리($1 \le K \le 100$, $K \le N^2$)가 있고, 각 소는 서로 다른 목초지에 있다. 어떤 두 소는 길을 건너지 않고서는 만나지 못할 수도 있다. 이런 소가 몇 쌍인지 세어 보자.

첫째 줄에 $N$, $K$, $R$이 주어진다.

다음 $R$개의 줄에는 길이 한 줄에 하나씩 주어진다. 각 길은 상하좌우로 인접한 두 목초지를 잇고, $r$ $c$ $r'$ $c'$ (행, 열, 행, 열) 형태로 주어진다. 각 수는 $1$ 이상 $N$ 이하이다.

그다음 $K$개의 줄에는 소의 위치가 한 줄에 하나씩 행과 열 순서로 주어진다.

길을 건너지 않고서는 만날 수 없는 소가 몇 쌍인지 출력한다.