시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 279 93 75 36.408%

문제

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

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

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

입력

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

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

출력

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

예제 입력 1

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

예제 출력 1

Test case 1: 5
W3sicHJvYmxlbV9pZCI6IjM3NzAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzMDBcdWQ1NWNcdWJiZmNcdWFkNmQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjMwMFx1ZDU1Y1x1YmJmY1x1YWQ2ZFx1Yzc0MCBcdWIzZDlcdWM1NDRcdWMyZGNcdWM1NDRcdWM1ZDAgXHVjNzA0XHVjZTU4XHVkNTVjIFx1ZDU1Y1x1YmMxOFx1YjNjNFx1YzVkMCBcdWM3MDRcdWNlNThcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiAzXHViYTc0XHVjNzc0IFx1YmMxNFx1YjJlNFx1Yzc3OCBcdWQ1NWNcdWFkNmRcdWM3NTggXHVjMTFjXHVjYWJkXHVjNzNjXHViODVjIFx1YzExY1x1ZDU3NCwgXHViM2Q5XHVjYWJkXHVjNzNjXHViODVjIFx1YjNkOVx1ZDU3NCwgXHViMGE4XHVjYWJkXHVjNzNjXHViODVjIFx1YjBhOFx1ZDU3NFx1YzVkMCBcdWM3NThcdWQ1NzQgXHViNDU4XHViN2VjXHVjMmY4XHVjNWVjIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMzAwXHVkNTVjXHViYmZjXHVhZDZkXHVjNzU4IFx1YjNkOVx1ZDU3NFx1YzU0OFx1YzVkMFx1YjI5NCBcdWIzYzRcdWMyZGNcdWFjMDAgTlx1YWMxYyBcdWM3ODhcdWFjZTAsIFx1YzExY1x1ZDU3NFx1YzU0OFx1YzVkMFx1YjI5NCBcdWIzYzRcdWMyZGNcdWFjMDAgTVx1YWMxYyBcdWM3ODhcdWIyZTQuIChNICZsZTsgMTAwMCwgTiAmbGU7IDEwMDApIFx1YWMwMSBcdWIzYzRcdWMyZGNcdWIyOTQgXHViZDgxXHVjYWJkXHViZDgwXHVkMTMwIFx1YjBhOFx1Y2FiZFx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0LiBcdWMwYzhcdWI4NWMgXHVjZGU4XHVjNzg0XHVkNTVjIFx1YjMwMFx1ZDFiNVx1YjgzOVx1Yzc0MCBcdWMxMWNcdWQ1NzRcdWM1NDhcdWFjZmMgXHViM2Q5XHVkNTc0XHVjNTQ4XHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBLXHVhYzFjXHVjNzU4IFx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWFjMDEgXHVhY2UwXHVjMThkXHViM2M0XHViODVjXHViMjk0IFx1YjNkOVx1ZDU3NFx1YzU0OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViM2M0XHVjMmRjXHVjNjQwIFx1YzExY1x1ZDU3NFx1YzU0OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViM2M0XHVjMmRjXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWM3N2NcdWM5YzFcdWMxMjAgXHViM2M0XHViODVjXHVjNzc0XHViMmU0LiAoXHVjNmQwXHViNzk4IFx1Yzc3Y1x1YzljMVx1YzEyMFx1Yzc3OCBcdWIzYzRcdWI4NWNcdWIyOTQgXHVjNmI0XHVjODA0XHVjMGFjXHViOTdjIFx1YzljMFx1YjhlOFx1ZDU1OFx1YWM4YyBcdWQ1NThcdWFjZTAgXHVkNTNjXHViODVjXHVhYzEwXHVjNzQ0IFx1YjI5MFx1YjA3Y1x1YWM4YyBcdWQ1NThcdWM1ZWMgXHVjMGFjXHVhY2UwXHVjNzU4IFx1YzZkMFx1Yzc3OFx1Yzc3NCBcdWI0MThcdWJiYzBcdWI4NWMsIFx1Yzc3Y1x1YmQ4MFx1YjdlYyBcdWFjZTBcdWM4MDBcdWI5N2MgXHViOWNjXHViNGU0XHVhYzcwXHViMDk4IFx1Y2VlNFx1YmUwY1x1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWMxMWMgXHVhZGY4XHViN2VjXHVkNTVjIFx1Yzc3Y1x1Yzc3NCBcdWM3N2NcdWM1YjRcdWIwOThcdWM5YzAgXHVjNTRhXHViM2M0XHViODVkIFx1YzEyNFx1YWNjNFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQpPFwvcD5cclxuXHJcbjxwPlx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1Y1x1YWMwMCBcdWMxMWNcdWI4NWMgXHVhZDUwXHVjYzI4XHVkNTU4XHViMjk0IFx1YWNmM1x1YzVkMFx1YjI5NCBcdWQ3MzRcdWFjOGNcdWMxOGNcdWI5N2MgXHVjOWMwXHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVkNTVjIFx1YzgxMFx1YzVkMFx1YzExYyBcdWFkNTBcdWNjMjhcdWQ1NThcdWIyOTQgXHVhY2UwXHVjMThkXHViM2M0XHViODVjXHViMjk0IFx1Y2Q1Y1x1YjMwMCAyXHVhYzFjXHVjNzc0XHViMmU0LiBcdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhY2UwXHVjMThkXHViM2M0XHViODVjXHVhYzAwIFx1YWQ1MFx1Y2MyOFx1ZDU1OFx1YjI5NCBcdWFjZjNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgTiwgTSwgS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIEtcdWIyOTQgXHVhY2UwXHVjMThkXHViM2M0XHViODVjXHVjNzU4IFx1YzIxOFx1Yzc3NFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBLXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWNcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhY2UwXHVjMThkXHViM2M0XHViODVjXHVjNzU4IFx1YzgxNVx1YmNmNFx1YjI5NCBcdWMyMmJcdWM3OTAgMlx1YWMxY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWIzZDlcdWQ1NzRcdWM1NDhcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWJjODhcdWQ2MzhcdWM3NzRcdWFjZTAsIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHViMjk0IFx1YzExY1x1ZDU3NFx1YzU0OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViM2M0XHVjMmRjXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhY2UwXHVjMThkXHViM2M0XHViODVjXHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCA0MFx1YjljY1x1YWMxY1x1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzNjXHViYTcwLCBcdWJiMzhcdWM4MWNcdWM3NTggXHVjODE1XHViMmY1XHVjNzc0IDI8c3VwPjYzPFwvc3VwPi0xXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVhY2JkXHVjNmIwXHViOWNjIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWFkNTBcdWNjMjhcdWM4MTBcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWJjODhcdWQ2MzhcdWM2NDAgXHVkNTY4XHVhZWQ4IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzNzcwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSmFwYW4iLCJkZXNjcmlwdGlvbiI6IjxwPkphcGFuIHBsYW5zIHRvIHdlbGNvbWUgdGhlIEFDTSBJQ1BDIFdvcmxkIEZpbmFscyBhbmQgYSBsb3Qgb2Ygcm9hZHMgbXVzdCBiZSBidWlsdCBmb3IgdGhlIHZlbnVlLiBKYXBhbiBpcyB0YWxsIGlzbGFuZCB3aXRoIE4gY2l0aWVzIG9uIHRoZSBFYXN0IGNvYXN0IGFuZCBNIGNpdGllcyBvbiB0aGUgV2VzdCBjb2FzdCAoTSAmbGU7IDEwMDAsIE4gJmxlOyAxMDAwKS4gSyBzdXBlcmhpZ2h3YXlzIHdpbGwgYmUgYnVpbGQuIENpdGllcyBvbiBlYWNoIGNvYXN0IGFyZSBudW1iZXJlZCAxLCAyLCAuLi4gZnJvbSBOb3J0aCB0byBTb3V0aC4gRWFjaCBzdXBlcmhpZ2h3YXkgaXMgc3RyYWlnaHQgbGluZSBhbmQgY29ubmVjdHMgY2l0eSBvbiB0aGUgRWFzdCBjb2FzdCB3aXRoIGNpdHkgb2YgdGhlIFdlc3QgY29hc3QuIFRoZSBmdW5kaW5nIGZvciB0aGUgY29uc3RydWN0aW9uIGlzIGd1YXJhbnRlZWQgYnkgQUNNLiBBIG1ham9yIHBvcnRpb24gb2YgdGhlIHN1bSBpcyBkZXRlcm1pbmVkIGJ5IHRoZSBudW1iZXIgb2YgY3Jvc3NpbmdzIGJldHdlZW4gc3VwZXJoaWdod2F5cy4gQXQgbW9zdCB0d28gc3VwZXJoaWdod2F5cyBjcm9zcyBhdCBvbmUgbG9jYXRpb24uIFdyaXRlIGEgcHJvZ3JhbSB0aGF0IGNhbGN1bGF0ZXMgdGhlIG51bWJlciBvZiB0aGUgY3Jvc3NpbmdzIGJldHdlZW4gc3VwZXJoaWdod2F5cy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBmaWxlIHN0YXJ0cyB3aXRoIFQgLSB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIHN0YXJ0cyB3aXRoIHRocmVlIG51bWJlcnMgJm5kYXNoOyBOLCBNLCBLLiBFYWNoIG9mIHRoZSBuZXh0IEsgbGluZXMgY29udGFpbnMgdHdvIG51bWJlcnMgJm5kYXNoOyB0aGUgbnVtYmVycyBvZiBjaXRpZXMgY29ubmVjdGVkIGJ5IHRoZSBzdXBlcmhpZ2h3YXkuIFRoZSBmaXJzdCBvbmUgaXMgdGhlIG51bWJlciBvZiB0aGUgY2l0eSBvbiB0aGUgRWFzdCBjb2FzdCBhbmQgc2Vjb25kIG9uZSBpcyB0aGUgbnVtYmVyIG9mIHRoZSBjaXR5IG9mIHRoZSBXZXN0IGNvYXN0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSB3cml0ZSBvbmUgbGluZSBvbiB0aGUgc3RhbmRhcmQgb3V0cHV0OiZuYnNwOzxcL3A+XHJcblxyXG48cHJlPlxyXG5UZXN0IGNhc2UgJmx0O2Nhc2UgbnVtYmVyJmd0OzogJmx0O251bWJlciBvZiBjcm9zc2luZ3MmZ3Q7PFwvcHJlPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

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