시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 548 256 201 47.183%

문제

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

존의 농장에 대대적인 개편이 있었다. 이제 작은 정사각형 목초지가 N×N (2 ≤ N ≤ 100) 격자로 이루어져 있다. 인접한 목초지 사이는 일반적으로 자유롭게 건너갈 수 있지만, 그 중 일부는 길을 건너야 한다. 농장의 바깥에는 높은 울타리가 있어서 소가 농장 밖으로 나갈 일은 없다.

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

입력

첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. 그 다음 K줄에는 한 줄의 하나씩 소의 위치가 행과 열로 주어진다.

출력

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

예제 입력 1

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

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjE0NDY2IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMThjXHVhYzAwIFx1YWUzOFx1Yzc0NCBcdWFjNzRcdWIxMDhcdWFjMDQgXHVjNzc0XHVjNzIwIDYiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzE4Y1x1YWMwMCBcdWFlMzhcdWM3NDQgXHVhYzc0XHViMTA4XHVhYzA0IFx1Yzc3NFx1YzcyMFx1YjI5NCBcdWFkZjhcdWIwZTUgXHVhZTM4XHVjNzc0IFx1YjljZVx1YzU0NFx1YzExY1x1Yzc3NFx1YjJlNC4gXHVjODc0XHVjNzU4IFx1YjE4ZFx1YzdhNVx1YzVkMFx1YjI5NCBcdWFlMzhcdWM3NzQgXHViMTA4XHViYjM0IFx1YjljZVx1YzU0NFx1YzExYywgXHVhZTM4XHVjNzQ0IFx1YWM3NFx1YjEwOFx1YzljMCBcdWM1NGFcdWFjZTBcdWMxMWNcdWIyOTQgXHViY2M0XHViODVjIFx1YjNjY1x1YzU0NFx1YjJlNFx1YjJkMCBcdWMyMThcdWFjMDAgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4NzRcdWM3NTggXHViMThkXHVjN2E1XHVjNWQwIFx1YjMwMFx1YjMwMFx1YzgwMVx1Yzc3OCBcdWFjMWNcdWQzYjhcdWM3NzQgXHVjNzg4XHVjNWM4XHViMmU0LiBcdWM3NzRcdWM4MWMgXHVjNzkxXHVjNzQwIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWJhYTlcdWNkMDhcdWM5YzBcdWFjMDAgTiZ0aW1lcztOICgyICZsZTsgTiAmbGU7IDEwMCkgXHVhY2E5XHVjNzkwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWJhYTlcdWNkMDhcdWM5YzAgXHVjMGFjXHVjNzc0XHViMjk0IFx1Yzc3Y1x1YmMxOFx1YzgwMVx1YzczY1x1Yjg1YyBcdWM3OTBcdWM3MjBcdWI4NmRcdWFjOGMgXHVhYzc0XHViMTA4XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWM5YzBcdWI5Y2MsIFx1YWRmOCBcdWM5MTEgXHVjNzdjXHViZDgwXHViMjk0IFx1YWUzOFx1Yzc0NCBcdWFjNzRcdWIxMDhcdWM1N2MgXHVkNTVjXHViMmU0LiA8YSBocmVmPVwiaHR0cHM6XC9cL3d3dy5hY21pY3BjLm5ldFwvcHJvYmxlbVwvMTQ0NjlcIj5cdWIxOGRcdWM3YTVcdWM3NTggXHViYzE0XHVhZTY1XHVjNWQwXHViMjk0IFx1YjE5Mlx1Yzc0MCBcdWM2YjhcdWQwYzBcdWI5YWM8XC9hPlx1YWMwMCBcdWM3ODhcdWM1YjRcdWMxMWMgXHVjMThjXHVhYzAwIFx1YjE4ZFx1YzdhNSBcdWJjMTZcdWM3M2NcdWI4NWMgXHViMDk4XHVhYzA4IFx1Yzc3Y1x1Yzc0MCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPktcdWI5YzhcdWI5YWNcdWM3NTggKDEgJmxlOyBLICZsZTsgMTAwLEsgJmxlOyBOPHN1cD4yPFwvc3VwPikgXHVjMThjXHVhYzAwIFx1Yzg3NFx1Yzc1OCBcdWIxOGRcdWM3YTVcdWM1ZDAgXHVjNzg4XHVhY2UwLCBcdWFjMDEgXHVjMThjXHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViYWE5XHVjZDA4XHVjOWMwXHVjNWQwIFx1Yzc4OFx1YjJlNC4gXHVjNWI0XHViNWE0IFx1YjQ1MCBcdWMxOGNcdWIyOTQgXHVhZTM4XHVjNzQ0IFx1YWM3NFx1YjEwOFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzQgXHViOWNjXHViMDk4XHVjOWMwIFx1YmFiYiBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViN2YwIFx1YzE4Y1x1YWMwMCBcdWJhODcgXHVjMzBkXHVjNzc4XHVjOWMwIFx1YzEzOFx1YzViNFx1YmNmNFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgTiwgSywgUlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBSXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YWUzOFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWUzOFx1Yzc0MCBcdWMwYzFcdWQ1NThcdWM4OGNcdWM2YjBcdWI4NWMgXHVjNzc4XHVjODExXHVkNTVjIFx1YjQ1MCBcdWJhYTlcdWNkMDhcdWM5YzBcdWI5N2MgXHVjNzg3XHVhY2UwLCByJm5ic3A7YyZuYnNwO3ImcHJpbWU7IGMmcHJpbWU7XHVjNzU4IFx1ZDYxNVx1ZDBkYyAoXHVkNTg5LCBcdWM1ZjQsIFx1ZDU4OSwgXHVjNWY0KVx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWMyMThcdWIyOTQgMSBcdWM3NzRcdWMwYzEgTiBcdWM3NzRcdWQ1NThcdWM3NzRcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMgS1x1YzkwNFx1YzVkMFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHVjNzU4IFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWMxOGNcdWM3NTggXHVjNzA0XHVjZTU4XHVhYzAwIFx1ZDU4OVx1YWNmYyBcdWM1ZjRcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWUzOFx1Yzc0NCBcdWFjNzRcdWIxMDhcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTc0IFx1YjljY1x1YjBhMCBcdWMyMTggXHVjNWM2XHViMjk0IFx1YzE4Y1x1YWMwMCBcdWJhODcgXHVjMzBkXHVjNzc4XHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE0NDY2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiV2h5IERpZCB0aGUgQ293IENyb3NzIHRoZSBSb2FkIElJSSAoU2lsdmVyKSIsImRlc2NyaXB0aW9uIjoiPHA+V2h5IGRpZCB0aGUgY293IGNyb3NzIHRoZSByb2FkPyBXZWxsLCBvbmUgcmVhc29uIGlzIHRoYXQgRmFybWVyIEpvaG4mIzM5O3MgZmFybSBzaW1wbHkgaGFzIGEgbG90IG9mIHJvYWRzLCBtYWtpbmcgaXQgaW1wb3NzaWJsZSBmb3IgaGlzIGNvd3MgdG8gdHJhdmVsIGFyb3VuZCB3aXRob3V0IGNyb3NzaW5nIG1hbnkgb2YgdGhlbS48XC9wPlxyXG5cclxuPHA+RkomIzM5O3MgZmFybSBpcyBhcnJhbmdlZCBhcyBhbiZuYnNwO04mdGltZXM7TiBzcXVhcmUgZ3JpZCBvZiBmaWVsZHMgKDIgJmxlOyBOICZsZTsgMTAwKSwgQ2VydGFpbiBwYWlycyBvZiBhZGphY2VudCBmaWVsZHMgKGUuZy4sIG5vcnRoLXNvdXRoIG9yIGVhc3Qtd2VzdCkgYXJlIHNlcGFyYXRlZCBieSByb2FkcywgYW5kIGEgdGFsbCBmZW5jZSBydW5zIGFyb3VuZCB0aGUgZXh0ZXJuYWwgcGVyaW1ldGVyIG9mIHRoZSBlbnRpcmUgZ3JpZCwgcHJldmVudGluZyBjb3dzIGZyb20gbGVhdmluZyB0aGUgZmFybS4gQ293cyBjYW4gbW92ZSBmcmVlbHkgZnJvbSBhbnkgZmllbGQgdG8gYW55IG90aGVyIGFkamFjZW50IGZpZWxkIChub3J0aCwgZWFzdCwgc291dGgsIG9yIHdlc3QpLCBhbHRob3VnaCB0aGV5IHByZWZlciBub3QgdG8gY3Jvc3Mgcm9hZHMgdW5sZXNzIGFic29sdXRlbHkgbmVjZXNzYXJ5LjxcL3A+XHJcblxyXG48cD5UaGVyZSBhcmUmbmJzcDtLJm5ic3A7Y293cyAoMSAmbGU7IEsgJmxlOyAxMDAsSyAmbGU7IE48c3VwPjI8XC9zdXA+KSBvbiBGSiYjMzk7cyBmYXJtLCBlYWNoIGxvY2F0ZWQgaW4gYSBkaWZmZXJlbnQgZmllbGQuIEEgcGFpciBvZiBjb3dzIGlzIHNhaWQgdG8gYmUgJnF1b3Q7ZGlzdGFudCZxdW90OyBpZiwgaW4gb3JkZXIgZm9yIG9uZSBjb3cgdG8gdmlzaXQgdGhlIG90aGVyLCBpdCBpcyBuZWNlc3NhcnkgdG8gY3Jvc3MgYXQgbGVhc3Qgb25lIHJvYWQuIFBsZWFzZSBoZWxwIEZKIGNvdW50IHRoZSBudW1iZXIgb2YgZGlzdGFudCBwYWlycyBvZiBjb3dzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMmbmJzcDtOLCZuYnNwO0ssIGFuZCZuYnNwO1IuIFRoZSBuZXh0Jm5ic3A7UiZuYnNwO2xpbmVzIGRlc2NyaWJlJm5ic3A7UiZuYnNwO3JvYWRzIHRoYXQgZXhpc3QgYmV0d2VlbiBwYWlycyBvZiBhZGphY2VudCBmaWVsZHMuIEVhY2ggbGluZSBpcyBvZiB0aGUgZm9ybSByJm5ic3A7YyZuYnNwO3ImcHJpbWU7IGMmcHJpbWU7IChpbnRlZ2VycyBpbiB0aGUgcmFuZ2UmbmJzcDsxJmhlbGxpcDtOKSwgaW5kaWNhdGluZyBhIHJvYWQgYmV0d2VlbiB0aGUgZmllbGQgaW4gKHJvdyZuYnNwO3IsIGNvbHVtbiZuYnNwO2MpIGFuZCB0aGUgYWRqYWNlbnQgZmllbGQgaW4gKHJvdyZuYnNwO3ImcHJpbWU7LCBjb2x1bW4mbmJzcDtjJnByaW1lOykuIFRoZSBmaW5hbCZuYnNwO0smbmJzcDtsaW5lcyBpbmRpY2F0ZSB0aGUgbG9jYXRpb25zIG9mIHRoZSZuYnNwO0smbmJzcDtjb3dzLCBlYWNoIHNwZWNpZmllZCBpbiB0ZXJtcyBvZiBhIHJvdyBhbmQgY29sdW1uLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlByaW50IHRoZSBudW1iZXIgb2YgcGFpcnMgb2YgY293cyB0aGF0IGFyZSBkaXN0YW50LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d