시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 194 52 46 31.944%

문제

대한민국은 동아시아에 위치한 한반도에 위치하고 있다. 3면이 바다인 한국의 서쪽으로 서해, 동쪽으로 동해, 남쪽으로 남해에 의해 둘러싸여 있다.

대한민국의 동해안에는 도시가 N개 있고, 서해안에는 도시가 M개 있다. (M ≤ 1000, N ≤ 1000) 각 도로는 북쪽부터 남쪽까지 번호가 1번부터 매겨져 있다. 새로 취임한 대통령은 서해안과 동해안을 연결하는 K개의 고속도로를 만들려고 한다. 각 고속도로는 동해안에 있는 도시와 서해안에 있는 도시를 연결하는 일직선 도로이다. (원래 일직선인 도로는 운전사를 지루하게 하고 피로감을 느끼게 하여 사고의 원인이 되므로, 일부러 고저를 만들거나 커브를 만들어서 그러한 일이 일어나지 않도록 설계되어 있다)

고속도로가 서로 교차하는 곳에는 휴게소를 지으려고 한다. 한 점에서 교차하는 고속도로는 최대 2개이다. 고속도로가 주어졌을 때, 고속도로가 교차하는 곳의 개수를 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 N, M, K가 주어진다. K는 고속도로의 수이다. 둘째 줄부터 K개의 줄에는 고속도로의 정보가 주어진다. 고속도로의 정보는 숫자 2개로 이루어져 있다. 첫 번째 숫자는 동해안에 있는 도시의 번호이고, 두 번째 숫자는 서해안에 있는 도시의 번호이다.

고속도로의 개수는 40만개보다 작거나 같으며, 문제의 정답dl 263-1보다 작거나 같은 경우만 입력으로 주어진다.

출력

각 테스트 케이스에 대해서, 교차점의 수를 케이스 번호와 함께 출력한다.

예제 입력 1

1
3 4 4
1 4
2 3
3 2
3 1

예제 출력 1

Test case 1: 5
W3sicHJvYmxlbV9pZCI6IjM3NzAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzMDBcdWQ1NWNcdWJiZmNcdWFkNmQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjMwMFx1ZDU1Y1x1YmJmY1x1YWQ2ZFx1Yzc0MCBcdWIzZDlcdWM1NDRcdWMyZGNcdWM1NDRcdWM1ZDAgXHVjNzA0XHVjZTU4XHVkNTVjIFx1ZDU1Y1x1YmMxOFx1YjNjNFx1YzVkMCBcdWM3MDRcdWNlNThcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiAzXHViYTc0XHVjNzc0IFx1YmMxNFx1YjJlNFx1Yzc3OCBcdWQ1NWNcdWFkNmRcdWM3NTggXHVjMTFjXHVjYWJkXHVjNzNjXHViODVjIFx1YzExY1x1ZDU3NCwgXHViM2Q5XHVjYWJkXHVjNzNjXHViODVjIFx1YjNkOVx1ZDU3NCwgXHViMGE4XHVjYWJkXHVjNzNjXHViODVjIFx1YjBhOFx1ZDU3NFx1YzVkMCBcdWM3NThcdWQ1NzQgXHViNDU4XHViN2VjXHVjMmY4XHVjNWVjIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMzAwXHVkNTVjXHViYmZjXHVhZDZkXHVjNzU4IFx1YjNkOVx1ZDU3NFx1YzU0OFx1YzVkMFx1YjI5NCBcdWIzYzRcdWMyZGNcdWFjMDAgTlx1YWMxYyBcdWM3ODhcdWFjZTAsIFx1YzExY1x1ZDU3NFx1YzU0OFx1YzVkMFx1YjI5NCBcdWIzYzRcdWMyZGNcdWFjMDAgTVx1YWMxYyBcdWM3ODhcdWIyZTQuIChNICZsZTsgMTAwMCwgTiAmbGU7IDEwMDApIFx1YWMwMSBcdWIzYzRcdWI4NWNcdWIyOTQgXHViZDgxXHVjYWJkXHViZDgwXHVkMTMwIFx1YjBhOFx1Y2FiZFx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0LiBcdWMwYzhcdWI4NWMgXHVjZGU4XHVjNzg0XHVkNTVjIFx1YjMwMFx1ZDFiNVx1YjgzOVx1Yzc0MCBcdWMxMWNcdWQ1NzRcdWM1NDhcdWFjZmMgXHViM2Q5XHVkNTc0XHVjNTQ4XHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBLXHVhYzFjXHVjNzU4IFx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWFjMDEgXHVhY2UwXHVjMThkXHViM2M0XHViODVjXHViMjk0IFx1YjNkOVx1ZDU3NFx1YzU0OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViM2M0XHVjMmRjXHVjNjQwIFx1YzExY1x1ZDU3NFx1YzU0OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViM2M0XHVjMmRjXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWM3N2NcdWM5YzFcdWMxMjAgXHViM2M0XHViODVjXHVjNzc0XHViMmU0LiAoXHVjNmQwXHViNzk4IFx1Yzc3Y1x1YzljMVx1YzEyMFx1Yzc3OCBcdWIzYzRcdWI4NWNcdWIyOTQgXHVjNmI0XHVjODA0XHVjMGFjXHViOTdjIFx1YzljMFx1YjhlOFx1ZDU1OFx1YWM4YyBcdWQ1NThcdWFjZTAgXHVkNTNjXHViODVjXHVhYzEwXHVjNzQ0IFx1YjI5MFx1YjA3Y1x1YWM4YyBcdWQ1NThcdWM1ZWMgXHVjMGFjXHVhY2UwXHVjNzU4IFx1YzZkMFx1Yzc3OFx1Yzc3NCBcdWI0MThcdWJiYzBcdWI4NWMsIFx1Yzc3Y1x1YmQ4MFx1YjdlYyBcdWFjZTBcdWM4MDBcdWI5N2MgXHViOWNjXHViNGU0XHVhYzcwXHViMDk4IFx1Y2VlNFx1YmUwY1x1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWMxMWMgXHVhZGY4XHViN2VjXHVkNTVjIFx1Yzc3Y1x1Yzc3NCBcdWM3N2NcdWM1YjRcdWIwOThcdWM5YzAgXHVjNTRhXHViM2M0XHViODVkIFx1YzEyNFx1YWNjNFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQpPFwvcD5cclxuXHJcbjxwPlx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1Y1x1YWMwMCBcdWMxMWNcdWI4NWMgXHVhZDUwXHVjYzI4XHVkNTU4XHViMjk0IFx1YWNmM1x1YzVkMFx1YjI5NCBcdWQ3MzRcdWFjOGNcdWMxOGNcdWI5N2MgXHVjOWMwXHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVkNTVjIFx1YzgxMFx1YzVkMFx1YzExYyBcdWFkNTBcdWNjMjhcdWQ1NThcdWIyOTQgXHVhY2UwXHVjMThkXHViM2M0XHViODVjXHViMjk0IFx1Y2Q1Y1x1YjMwMCAyXHVhYzFjXHVjNzc0XHViMmU0LiBcdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhY2UwXHVjMThkXHViM2M0XHViODVjXHVhYzAwIFx1YWQ1MFx1Y2MyOFx1ZDU1OFx1YjI5NCBcdWFjZjNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgTiwgTSwgS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIEtcdWIyOTQgXHVhY2UwXHVjMThkXHViM2M0XHViODVjXHVjNzU4IFx1YzIxOFx1Yzc3NFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBLXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWNcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhY2UwXHVjMThkXHViM2M0XHViODVjXHVjNzU4IFx1YzgxNVx1YmNmNFx1YjI5NCBcdWMyMmJcdWM3OTAgMlx1YWMxY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWIzZDlcdWQ1NzRcdWM1NDhcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWJjODhcdWQ2MzhcdWM3NzRcdWFjZTAsIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHViMjk0IFx1YzExY1x1ZDU3NFx1YzU0OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViM2M0XHVjMmRjXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhY2UwXHVjMThkXHViM2M0XHViODVjXHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCA0MFx1YjljY1x1YWMxY1x1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzNjXHViYTcwLCBcdWJiMzhcdWM4MWNcdWM3NTggXHVjODE1XHViMmY1ZGwgMjxzdXA+NjM8XC9zdXA+LTFcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWFjYmRcdWM2YjBcdWI5Y2MgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YWQ1MFx1Y2MyOFx1YzgxMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZjAwXHVjNzc0XHVjMmE0IFx1YmM4OFx1ZDYzOFx1YzY0MCBcdWQ1NjhcdWFlZDggXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM3NzAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJKYXBhbiIsImRlc2NyaXB0aW9uIjoiPHA+SmFwYW4gcGxhbnMgdG8gd2VsY29tZSB0aGUgQUNNIElDUEMgV29ybGQgRmluYWxzIGFuZCBhIGxvdCBvZiByb2FkcyBtdXN0IGJlIGJ1aWx0IGZvciB0aGUgdmVudWUuIEphcGFuIGlzIHRhbGwgaXNsYW5kIHdpdGggTiBjaXRpZXMgb24gdGhlIEVhc3QgY29hc3QgYW5kIE0gY2l0aWVzIG9uIHRoZSBXZXN0IGNvYXN0IChNICZsZTsgMTAwMCwgTiAmbGU7IDEwMDApLiBLIHN1cGVyaGlnaHdheXMgd2lsbCBiZSBidWlsZC4gQ2l0aWVzIG9uIGVhY2ggY29hc3QgYXJlIG51bWJlcmVkIDEsIDIsIC4uLiBmcm9tIE5vcnRoIHRvIFNvdXRoLiBFYWNoIHN1cGVyaGlnaHdheSBpcyBzdHJhaWdodCBsaW5lIGFuZCBjb25uZWN0cyBjaXR5IG9uIHRoZSBFYXN0IGNvYXN0IHdpdGggY2l0eSBvZiB0aGUgV2VzdCBjb2FzdC4gVGhlIGZ1bmRpbmcgZm9yIHRoZSBjb25zdHJ1Y3Rpb24gaXMgZ3VhcmFudGVlZCBieSBBQ00uIEEgbWFqb3IgcG9ydGlvbiBvZiB0aGUgc3VtIGlzIGRldGVybWluZWQgYnkgdGhlIG51bWJlciBvZiBjcm9zc2luZ3MgYmV0d2VlbiBzdXBlcmhpZ2h3YXlzLiBBdCBtb3N0IHR3byBzdXBlcmhpZ2h3YXlzIGNyb3NzIGF0IG9uZSBsb2NhdGlvbi4gV3JpdGUgYSBwcm9ncmFtIHRoYXQgY2FsY3VsYXRlcyB0aGUgbnVtYmVyIG9mIHRoZSBjcm9zc2luZ3MgYmV0d2VlbiBzdXBlcmhpZ2h3YXlzLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGZpbGUgc3RhcnRzIHdpdGggVCAtIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2Ugc3RhcnRzIHdpdGggdGhyZWUgbnVtYmVycyAmbmRhc2g7IE4sIE0sIEsuIEVhY2ggb2YgdGhlIG5leHQgSyBsaW5lcyBjb250YWlucyB0d28gbnVtYmVycyAmbmRhc2g7IHRoZSBudW1iZXJzIG9mIGNpdGllcyBjb25uZWN0ZWQgYnkgdGhlIHN1cGVyaGlnaHdheS4gVGhlIGZpcnN0IG9uZSBpcyB0aGUgbnVtYmVyIG9mIHRoZSBjaXR5IG9uIHRoZSBFYXN0IGNvYXN0IGFuZCBzZWNvbmQgb25lIGlzIHRoZSBudW1iZXIgb2YgdGhlIGNpdHkgb2YgdGhlIFdlc3QgY29hc3QuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlIHdyaXRlIG9uZSBsaW5lIG9uIHRoZSBzdGFuZGFyZCBvdXRwdXQ6Jm5ic3A7PFwvcD5cclxuXHJcbjxwcmU+XHJcblRlc3QgY2FzZSAmbHQ7Y2FzZSBudW1iZXImZ3Q7OiAmbHQ7bnVtYmVyIG9mIGNyb3NzaW5ncyZndDs8XC9wcmU+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ICPC > Regionals > Europe > Southeastern European Regional Contest > SEERC 2006 H번