시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblxyXG48cD5cclxuXHRcdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWNcdWFjMDAgXHVjMTFjXHViODVjIFx1YWQ1MFx1Y2MyOFx1ZDU1OFx1YjI5NCBcdWFjZjNcdWM1ZDBcdWIyOTQgXHVkNzM0XHVhYzhjXHVjMThjXHViOTdjIFx1YzljMFx1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1ZDU1YyBcdWM4MTBcdWM1ZDBcdWMxMWMgXHVhZDUwXHVjYzI4XHVkNTU4XHViMjk0IFx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1Y1x1YjI5NCBcdWNkNWNcdWIzMDAgMlx1YWMxY1x1Yzc3NFx1YjJlNC4gXHVhY2UwXHVjMThkXHViM2M0XHViODVjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1Y1x1YWMwMCBcdWFkNTBcdWNjMjhcdWQ1NThcdWIyOTQgXHVhY2YzXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IE4sIE0sIEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBLXHViMjk0IFx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWMyMThcdWM3NzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgS1x1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhY2UwXHVjMThkXHViM2M0XHViODVjXHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWM4MTVcdWJjZjRcdWIyOTQgXHVjMjJiXHVjNzkwIDJcdWFjMWNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjY2FiXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWIzZDlcdWQ1NzRcdWM1NDhcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWJjODhcdWQ2MzhcdWM3NzRcdWFjZTAsIFx1YjQ1MFx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWIyOTQgXHVjMTFjXHVkNTc0XHVjNTQ4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWIzYzRcdWMyZGNcdWM3NTggXHViYzg4XHVkNjM4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVhZDUwXHVjYzI4XHVjODEwXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNmMDBcdWM3NzRcdWMyYTQgXHViYzg4XHVkNjM4XHVjNjQwIFx1ZDU2OFx1YWVkOCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzc3MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkphcGFuIiwiZGVzY3JpcHRpb24iOiI8cD5KYXBhbiBwbGFucyB0byB3ZWxjb21lIHRoZSBBQ00gSUNQQyBXb3JsZCBGaW5hbHMgYW5kIGEgbG90IG9mIHJvYWRzIG11c3QgYmUgYnVpbHQgZm9yIHRoZSB2ZW51ZS4gSmFwYW4gaXMgdGFsbCBpc2xhbmQgd2l0aCBOIGNpdGllcyBvbiB0aGUgRWFzdCBjb2FzdCBhbmQgTSBjaXRpZXMgb24gdGhlIFdlc3QgY29hc3QgKE0gJmxlOyAxMDAwLCBOICZsZTsgMTAwMCkuIEsgc3VwZXJoaWdod2F5cyB3aWxsIGJlIGJ1aWxkLiBDaXRpZXMgb24gZWFjaCBjb2FzdCBhcmUgbnVtYmVyZWQgMSwgMiwgLi4uIGZyb20gTm9ydGggdG8gU291dGguIEVhY2ggc3VwZXJoaWdod2F5IGlzIHN0cmFpZ2h0IGxpbmUgYW5kIGNvbm5lY3RzIGNpdHkgb24gdGhlIEVhc3QgY29hc3Qgd2l0aCBjaXR5IG9mIHRoZSBXZXN0IGNvYXN0LiBUaGUgZnVuZGluZyBmb3IgdGhlIGNvbnN0cnVjdGlvbiBpcyBndWFyYW50ZWVkIGJ5IEFDTS4gQSBtYWpvciBwb3J0aW9uIG9mIHRoZSBzdW0gaXMgZGV0ZXJtaW5lZCBieSB0aGUgbnVtYmVyIG9mIGNyb3NzaW5ncyBiZXR3ZWVuIHN1cGVyaGlnaHdheXMuIEF0IG1vc3QgdHdvIHN1cGVyaGlnaHdheXMgY3Jvc3MgYXQgb25lIGxvY2F0aW9uLiBXcml0ZSBhIHByb2dyYW0gdGhhdCBjYWxjdWxhdGVzIHRoZSBudW1iZXIgb2YgdGhlIGNyb3NzaW5ncyBiZXR3ZWVuIHN1cGVyaGlnaHdheXMuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgZmlsZSBzdGFydHMgd2l0aCBUIC0gdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCB0aHJlZSBudW1iZXJzICZuZGFzaDsgTiwgTSwgSy4gRWFjaCBvZiB0aGUgbmV4dCBLIGxpbmVzIGNvbnRhaW5zIHR3byBudW1iZXJzICZuZGFzaDsgdGhlIG51bWJlcnMgb2YgY2l0aWVzIGNvbm5lY3RlZCBieSB0aGUgc3VwZXJoaWdod2F5LiBUaGUgZmlyc3Qgb25lIGlzIHRoZSBudW1iZXIgb2YgdGhlIGNpdHkgb24gdGhlIEVhc3QgY29hc3QgYW5kIHNlY29uZCBvbmUgaXMgdGhlIG51bWJlciBvZiB0aGUgY2l0eSBvZiB0aGUgV2VzdCBjb2FzdC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2Ugd3JpdGUgb25lIGxpbmUgb24gdGhlIHN0YW5kYXJkIG91dHB1dDombmJzcDs8XC9wPlxyXG5cclxuPHByZT5cclxuVGVzdCBjYXNlICZsdDtjYXNlIG51bWJlciZndDs6ICZsdDtudW1iZXIgb2YgY3Jvc3NpbmdzJmd0OzxcL3ByZT5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d