시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 118 32 28 33.333%

문제

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

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

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

입력

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

출력

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

예제 입력 1

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

예제 출력 1

Test case 1: 5
W3sicHJvYmxlbV9pZCI6IjM3NzAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzMDBcdWQ1NWNcdWJiZmNcdWFkNmQiLCJkZXNjcmlwdGlvbiI6IlxyXG48cD5cclxuXHRcdWIzMDBcdWQ1NWNcdWJiZmNcdWFkNmRcdWM3NDAgXHViM2Q5XHVjNTQ0XHVjMmRjXHVjNTQ0XHVjNWQwIFx1YzcwNFx1Y2U1OFx1ZDU1YyBcdWQ1NWNcdWJjMThcdWIzYzRcdWM1ZDAgXHVjNzA0XHVjZTU4XHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gM1x1YmE3NFx1Yzc3NCBcdWJjMTRcdWIyZTRcdWM3NzggXHVkNTVjXHVhZDZkXHVjNzU4IFx1YzExY1x1Y2FiZFx1YzczY1x1Yjg1YyBcdWMxMWNcdWQ1NzQsIFx1YjNkOVx1Y2FiZFx1YzczY1x1Yjg1YyBcdWIzZDlcdWQ1NzQsIFx1YjBhOFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWIwYThcdWQ1NzRcdWM1ZDAgXHVjNzU4XHVkNTc0IFx1YjQ1OFx1YjdlY1x1YzJmOFx1YzVlYyBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjMwMFx1ZDU1Y1x1YmJmY1x1YWQ2ZFx1Yzc1OCBcdWIzZDlcdWQ1NzRcdWM1NDhcdWM1ZDBcdWIyOTQgXHViM2M0XHVjMmRjXHVhYzAwIE5cdWFjMWMgXHVjNzg4XHVhY2UwLCBcdWMxMWNcdWQ1NzRcdWM1NDhcdWM1ZDBcdWIyOTQgXHViM2M0XHVjMmRjXHVhYzAwIE1cdWFjMWMgXHVjNzg4XHViMmU0LiAoTSAmbGU7IDEwMDAsIE4gJmxlOyAxMDAwKSBcdWFjMDEgXHViM2M0XHViODVjXHViMjk0IFx1YmQ4MVx1Y2FiZFx1YmQ4MFx1ZDEzMCBcdWIwYThcdWNhYmRcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIDFcdWJjODhcdWJkODBcdWQxMzAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjMGM4XHViODVjIFx1Y2RlOFx1Yzc4NFx1ZDU1YyBcdWIzMDBcdWQxYjVcdWI4MzlcdWM3NDAgXHVjMTFjXHVkNTc0XHVjNTQ4XHVhY2ZjIFx1YjNkOVx1ZDU3NFx1YzU0OFx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgS1x1YWMxY1x1Yzc1OCBcdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWNcdWI5N2MgXHViOWNjXHViNGRjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVhYzAxIFx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1Y1x1YjI5NCBcdWIzZDlcdWQ1NzRcdWM1NDhcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YjNjNFx1YzJkY1x1YzY0MCBcdWMxMWNcdWQ1NzRcdWM1NDhcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVjNzdjXHVjOWMxXHVjMTIwIFx1YjNjNFx1Yjg1Y1x1Yzc3NFx1YjJlNC4gKFx1YzZkMFx1Yjc5OCBcdWM3N2NcdWM5YzFcdWMxMjBcdWM3NzggXHViM2M0XHViODVjXHViMjk0IFx1YzZiNFx1YzgwNFx1YzBhY1x1Yjk3YyBcdWM5YzBcdWI4ZThcdWQ1NThcdWFjOGMgXHVkNTU4XHVhY2UwIFx1ZDUzY1x1Yjg1Y1x1YWMxMFx1Yzc0NCBcdWIyOTBcdWIwN2NcdWFjOGMgXHVkNTU4XHVjNWVjIFx1YzBhY1x1YWNlMFx1Yzc1OCBcdWM2ZDBcdWM3NzhcdWM3NzQgXHViNDE4XHViYmMwXHViODVjLCBcdWM3N2NcdWJkODBcdWI3ZWMgXHVhY2UwXHVjODAwXHViOTdjIFx1YjljY1x1YjRlNFx1YWM3MFx1YjA5OCBcdWNlZTRcdWJlMGNcdWI5N2MgXHViOWNjXHViNGU0XHVjNWI0XHVjMTFjIFx1YWRmOFx1YjdlY1x1ZDU1YyBcdWM3N2NcdWM3NzQgXHVjNzdjXHVjNWI0XHViMDk4XHVjOWMwIFx1YzU0YVx1YjNjNFx1Yjg1ZCBcdWMxMjRcdWFjYzRcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0KTxcL3A+XHJcblxyXG48cD5cclxuXHRcdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWNcdWFjMDAgXHVjMTFjXHViODVjIFx1YWQ1MFx1Y2MyOFx1ZDU1OFx1YjI5NCBcdWFjZjNcdWM1ZDBcdWIyOTQgXHVkNzM0XHVhYzhjXHVjMThjXHViOTdjIFx1YzljMFx1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1ZDU1YyBcdWM4MTBcdWM1ZDBcdWMxMWMgXHVhZDUwXHVjYzI4XHVkNTU4XHViMjk0IFx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1Y1x1YjI5NCBcdWNkNWNcdWIzMDAgMlx1YWMxY1x1Yzc3NFx1YjJlNC4gXHVhY2UwXHVjMThkXHViM2M0XHViODVjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1Y1x1YWMwMCBcdWFkNTBcdWNjMjhcdWQ1NThcdWIyOTQgXHVhY2YzXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IE4sIE0sIEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBLXHViMjk0IFx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWMyMThcdWM3NzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgS1x1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhY2UwXHVjMThkXHViM2M0XHViODVjXHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWM4MTVcdWJjZjRcdWIyOTQgXHVjMjJiXHVjNzkwIDJcdWFjMWNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWIyOTQgXHViM2Q5XHVkNTc0XHVjNTQ4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWIzYzRcdWMyZGNcdWM3NTggXHViYzg4XHVkNjM4XHVjNzc0XHVhY2UwLCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWMxMWNcdWQ1NzRcdWM1NDhcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWJjODhcdWQ2MzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWFkNTBcdWNjMjhcdWM4MTBcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWJjODhcdWQ2MzhcdWM2NDAgXHVkNTY4XHVhZWQ4IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNzcwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSmFwYW4iLCJkZXNjcmlwdGlvbiI6IjxwPkphcGFuIHBsYW5zIHRvIHdlbGNvbWUgdGhlIEFDTSBJQ1BDIFdvcmxkIEZpbmFscyBhbmQgYSBsb3Qgb2Ygcm9hZHMgbXVzdCBiZSBidWlsdCBmb3IgdGhlIHZlbnVlLiBKYXBhbiBpcyB0YWxsIGlzbGFuZCB3aXRoIE4gY2l0aWVzIG9uIHRoZSBFYXN0IGNvYXN0IGFuZCBNIGNpdGllcyBvbiB0aGUgV2VzdCBjb2FzdCAoTSAmbGU7IDEwMDAsIE4gJmxlOyAxMDAwKS4gSyBzdXBlcmhpZ2h3YXlzIHdpbGwgYmUgYnVpbGQuIENpdGllcyBvbiBlYWNoIGNvYXN0IGFyZSBudW1iZXJlZCAxLCAyLCAuLi4gZnJvbSBOb3J0aCB0byBTb3V0aC4gRWFjaCBzdXBlcmhpZ2h3YXkgaXMgc3RyYWlnaHQgbGluZSBhbmQgY29ubmVjdHMgY2l0eSBvbiB0aGUgRWFzdCBjb2FzdCB3aXRoIGNpdHkgb2YgdGhlIFdlc3QgY29hc3QuIFRoZSBmdW5kaW5nIGZvciB0aGUgY29uc3RydWN0aW9uIGlzIGd1YXJhbnRlZWQgYnkgQUNNLiBBIG1ham9yIHBvcnRpb24gb2YgdGhlIHN1bSBpcyBkZXRlcm1pbmVkIGJ5IHRoZSBudW1iZXIgb2YgY3Jvc3NpbmdzIGJldHdlZW4gc3VwZXJoaWdod2F5cy4gQXQgbW9zdCB0d28gc3VwZXJoaWdod2F5cyBjcm9zcyBhdCBvbmUgbG9jYXRpb24uIFdyaXRlIGEgcHJvZ3JhbSB0aGF0IGNhbGN1bGF0ZXMgdGhlIG51bWJlciBvZiB0aGUgY3Jvc3NpbmdzIGJldHdlZW4gc3VwZXJoaWdod2F5cy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBmaWxlIHN0YXJ0cyB3aXRoIFQgLSB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIHN0YXJ0cyB3aXRoIHRocmVlIG51bWJlcnMgJm5kYXNoOyBOLCBNLCBLLiBFYWNoIG9mIHRoZSBuZXh0IEsgbGluZXMgY29udGFpbnMgdHdvIG51bWJlcnMgJm5kYXNoOyB0aGUgbnVtYmVycyBvZiBjaXRpZXMgY29ubmVjdGVkIGJ5IHRoZSBzdXBlcmhpZ2h3YXkuIFRoZSBmaXJzdCBvbmUgaXMgdGhlIG51bWJlciBvZiB0aGUgY2l0eSBvbiB0aGUgRWFzdCBjb2FzdCBhbmQgc2Vjb25kIG9uZSBpcyB0aGUgbnVtYmVyIG9mIHRoZSBjaXR5IG9mIHRoZSBXZXN0IGNvYXN0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSB3cml0ZSBvbmUgbGluZSBvbiB0aGUgc3RhbmRhcmQgb3V0cHV0OiZuYnNwOzxcL3A+XHJcblxyXG48cHJlPlxyXG5UZXN0IGNhc2UgJmx0O2Nhc2UgbnVtYmVyJmd0OzogJmx0O251bWJlciBvZiBjcm9zc2luZ3MmZ3Q7PFwvcHJlPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=