시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB126605045.872%

문제

평소 그래프 이론에 관심이 많았던 주연이는 최근에 방향그래프에서 transitive closure를 계산하는 방법중 하나인 Warshall algorithm을 공부하였다. 주연이는 최근에 사귀게 된 남자친구 윤호가 얼마나 똑똑한지 시험하기 위해 transitive closure를 계산하는 방법을 윤호에게 물어보기로 결심했다. 질문의 내용은 아래와 같다.

"윤호오빠, ...

방향그래프 G = <V, E> (2<=|V|<=2,500. 1<=|E|<=10,000)가 주어졌을 때, G의 transitive closure는 0, 1로 구성된 V×V크기의 행렬 R로 표현할 수 있다. 만약 G의 두 정점 A와 B에 대해, A에서 B로 가는 경로가 존재하면 행렬R의 A행 B열의 값을 1로, 경로가 존재하지 않으면 0으로 채워넣는 것이다.

주어진 그래프 G에 대해 행렬 R을 구하여라. 단, R의 크기가 매우 커질 수 있으므로 그래프 G의 서로 다른 두 정점 X에서 Y에 대해, X에서 Y로 가는 경로가 존재하는 정점 쌍 (X, Y)의 개수를 출력하도록 한다. 즉, 그래프 G에 대한 행렬R에서 (행≠열)인 모든 셀에 대해 '1'로 채워진 셀의 개수를 출력한다.

오빠 할 수 있지 ?"

자신의 밑천이 주연이에게 드러날까 두려운 윤호는 여러분들에게 도움을 요청했다. 윤호와 주연이 사이를 갈라놓을지 말지는 여러분들의 손에 달렸다.

입력

입력의 첫 줄에는 테스트 케이스의 수 T (T<=10)가 주어진다.

각 테스트 케이스마다 첫 번째 줄에 정점과 간선의 수 N, M (2<=|V|<=2,500. 1<=|E|<=10,000)이 주어지고, 다음 M개의 줄에 각각 간선정보 A, B (1<=A, B<=N)가 주어진다. A에서 B로 가는 간선이 존재한다는 의미이다. 동일한 간선에 대한 입력이 중복으로 주어지지 않는다.

출력

각 테스트 케이스마다 한 줄에 X≠Y인 정점 X, Y에 대해 X에서 Y로 가는 경로가 존재하는 정점쌍 (X, Y)의 개수를 출력한다.

예제 입력 1

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

예제 출력 1

3
9

힌트

첫 번째 예제에 대해 주어진 그래프 G의 transitive closure를 계산한 행렬 R은 아래와 같다.

0 1 1
0 0 1
0 0 0

위 행렬에서 X≠Y인 정점쌍 (X, Y)는 3개 존재한다.

W3sicHJvYmxlbV9pZCI6Ijc4MjciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJUcmFuc2l0aXZlIENsb3N1cmUiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDNjOVx1YzE4YyBcdWFkZjhcdWI3OThcdWQ1MDQgXHVjNzc0XHViODYwXHVjNWQwIFx1YWQwMFx1YzJlY1x1Yzc3NCBcdWI5Y2VcdWM1NThcdWIzNTggXHVjOGZjXHVjNWYwXHVjNzc0XHViMjk0IFx1Y2Q1Y1x1YWRmY1x1YzVkMCBcdWJjMjlcdWQ1YTVcdWFkZjhcdWI3OThcdWQ1MDRcdWM1ZDBcdWMxMWMgPGEgaHJlZj1cImh0dHBzOlwvXC9lbi53aWtpcGVkaWEub3JnXC93aWtpXC9UcmFuc2l0aXZlX2Nsb3N1cmVcIj50cmFuc2l0aXZlIGNsb3N1cmU8XC9hPlx1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjOTExIFx1ZDU1OFx1YjA5OFx1Yzc3OCA8YSBocmVmPVwiaHR0cHM6XC9cL2VuLndpa2lwZWRpYS5vcmdcL3dpa2lcL0Zsb3lkJUUyJTgwJTkzV2Fyc2hhbGxfYWxnb3JpdGhtXCI+V2Fyc2hhbGwgYWxnb3JpdGhtPFwvYT5cdWM3NDQgXHVhY2Y1XHViZDgwXHVkNTU4XHVjNjAwXHViMmU0LiBcdWM4ZmNcdWM1ZjBcdWM3NzRcdWIyOTQgXHVjZDVjXHVhZGZjXHVjNWQwIFx1YzBhY1x1YWRjMFx1YWM4YyBcdWI0MWMgXHViMGE4XHVjNzkwXHVjZTVjXHVhZDZjIFx1YzcyNFx1ZDYzOFx1YWMwMCBcdWM1YmNcdWI5YzhcdWIwOTggXHViNjExXHViNjExXHVkNTVjXHVjOWMwIFx1YzJkY1x1ZDVkOFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgdHJhbnNpdGl2ZSBjbG9zdXJlXHViOTdjIFx1YWNjNFx1YzBiMFx1ZDU1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVjNzI0XHVkNjM4XHVjNWQwXHVhYzhjIFx1YmIzY1x1YzViNFx1YmNmNFx1YWUzMFx1Yjg1YyBcdWFjYjBcdWMyZWNcdWQ1ODhcdWIyZTQuIFx1YzljOFx1YmIzOFx1Yzc1OCBcdWIwYjRcdWM2YTlcdWM3NDAgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHA+JnF1b3Q7XHVjNzI0XHVkNjM4XHVjNjI0XHViZTYwLCAuLi48XC9wPlxyXG5cclxuPHA+XHViYzI5XHVkNWE1XHVhZGY4XHViNzk4XHVkNTA0IEcgPSAmbHQ7ViwgRSZndDsgKDImbHQ7PXxWfCZsdDs9Miw1MDAuIDEmbHQ7PXxFfCZsdDs9MTAsMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBHXHVjNzU4IHRyYW5zaXRpdmUgY2xvc3VyZVx1YjI5NCAwLCAxXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxYyBWJnRpbWVzO1ZcdWQwNmNcdWFlMzBcdWM3NTggXHVkNTg5XHViODJjIFJcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjljY1x1YzU3ZCBHXHVjNzU4IFx1YjQ1MCBcdWM4MTVcdWM4MTAgQVx1YzY0MCBCXHVjNWQwIFx1YjMwMFx1ZDU3NCwgQVx1YzVkMFx1YzExYyBCXHViODVjIFx1YWMwMFx1YjI5NCBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTU4XHViYTc0IFx1ZDU4OVx1YjgyY1JcdWM3NTggQVx1ZDU4OSBCXHVjNWY0XHVjNzU4IFx1YWMxMlx1Yzc0NCAxXHViODVjLCBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3NCAwXHVjNzNjXHViODVjIFx1Y2M0NFx1YzZjY1x1YjEyM1x1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzhmY1x1YzViNFx1YzljNCBcdWFkZjhcdWI3OThcdWQ1MDQgR1x1YzVkMCBcdWIzMDBcdWQ1NzQgXHVkNTg5XHViODJjIFJcdWM3NDQgXHVhZDZjXHVkNTU4XHVjNWVjXHViNzdjLiBcdWIyZTgsIFJcdWM3NTggXHVkMDZjXHVhZTMwXHVhYzAwIFx1YjllNFx1YzZiMCBcdWNlZTRcdWM5YzggXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmJjMFx1Yjg1YyBcdWFkZjhcdWI3OThcdWQ1MDQgR1x1Yzc1OCA8c3Ryb25nPlx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5Nzg8XC9zdHJvbmc+IFx1YjQ1MCBcdWM4MTVcdWM4MTAgWFx1YzVkMFx1YzExYyBZXHVjNWQwIFx1YjMwMFx1ZDU3NCwgWFx1YzVkMFx1YzExYyBZXHViODVjIFx1YWMwMFx1YjI5NCBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0IFx1YzgxNVx1YzgxMCBcdWMzMGQgKFgsIFkpXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWIzYzRcdWI4NWQgXHVkNTVjXHViMmU0LiBcdWM5ODksIFx1YWRmOFx1Yjc5OFx1ZDUwNCBHXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWQ1ODlcdWI4MmNSXHVjNWQwXHVjMTFjIChcdWQ1ODkmbmU7XHVjNWY0KVx1Yzc3OCBcdWJhYThcdWI0ZTAgXHVjMTQwXHVjNWQwIFx1YjMwMFx1ZDU3NCAmIzM5OzEmIzM5O1x1Yjg1YyBcdWNjNDRcdWM2Y2NcdWM5YzQgXHVjMTQwXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYyNFx1YmU2MCBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YzljMCA/JnF1b3Q7PFwvcD5cclxuXHJcbjxwPlx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWJjMTFcdWNjOWNcdWM3NzQgXHVjOGZjXHVjNWYwXHVjNzc0XHVjNWQwXHVhYzhjIFx1YjRkY1x1YjdlY1x1YjBhMFx1YWU0YyBcdWI0NTBcdWI4MjRcdWM2YjQgXHVjNzI0XHVkNjM4XHViMjk0IFx1YzVlY1x1YjdlY1x1YmQ4NFx1YjRlNFx1YzVkMFx1YWM4YyBcdWIzYzRcdWM2YzBcdWM3NDQgXHVjNjk0XHVjY2FkXHVkNTg4XHViMmU0LiBcdWM3MjRcdWQ2MzhcdWM2NDAgXHVjOGZjXHVjNWYwXHVjNzc0IFx1YzBhY1x1Yzc3NFx1Yjk3YyBcdWFjMDhcdWI3N2NcdWIxOTNcdWM3NDRcdWM5YzAgXHViOWQwXHVjOWMwXHViMjk0IFx1YzVlY1x1YjdlY1x1YmQ4NFx1YjRlNFx1Yzc1OCBcdWMxOTBcdWM1ZDAgXHViMmVjXHViODM4XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIHNyYz1cIlwvdXNlcnVwbG9hZFwvSGliYmFoXC8yMDE1MDRcL2Q5YjI5YzE0ZWYxZDdkNWQ2MGIzNTJhNGIxMTU5MTNlLmpwZ1wiIHN0eWxlPVwiaGVpZ2h0OjIxNy40Njk4Nzk1MTgwNzJweDsgd2lkdGg6MjAwcHhcIiBcLz48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4IFQgKFQmbHQ7PTEwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzgxNVx1YzgxMFx1YWNmYyBcdWFjMDRcdWMxMjBcdWM3NTggXHVjMjE4IE4sIE0gKDImbHQ7PXxWfCZsdDs9Miw1MDAuIDEmbHQ7PXxFfCZsdDs9MTAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YjJlNFx1Yzc0YyBNXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjMDFcdWFjMDEgXHVhYzA0XHVjMTIwXHVjODE1XHViY2Y0IEEsIEIgKDEmbHQ7PUEsIEImbHQ7PU4pXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gQVx1YzVkMFx1YzExYyBCXHViODVjIFx1YWMwMFx1YjI5NCBcdWFjMDRcdWMxMjBcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0XHViMjk0IFx1Yzc1OFx1YmJmOFx1Yzc3NFx1YjJlNC4gXHViM2Q5XHVjNzdjXHVkNTVjIFx1YWMwNFx1YzEyMFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjNzg1XHViODI1XHVjNzc0IFx1YzkxMVx1YmNmNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgWCZuZTtZXHVjNzc4IFx1YzgxNVx1YzgxMCBYLCBZXHVjNWQwIFx1YjMwMFx1ZDU3NCBYXHVjNWQwXHVjMTFjIFlcdWI4NWMgXHVhYzAwXHViMjk0IFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTQgXHVjODE1XHVjODEwXHVjMzBkIChYLCBZKVx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzYwOFx1YzgxY1x1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YWRmOFx1Yjc5OFx1ZDUwNCBHXHVjNzU4IHRyYW5zaXRpdmUgY2xvc3VyZVx1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NWMgXHVkNTg5XHViODJjIFJcdWM3NDAgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuMCAxIDFcclxuMCAwIDFcclxuMCAwIDBcclxuPFwvcHJlPlxyXG5cclxuPHA+XHVjNzA0IFx1ZDU4OVx1YjgyY1x1YzVkMFx1YzExYyBYJm5lO1lcdWM3NzggXHVjODE1XHVjODEwXHVjMzBkIChYLCBZKVx1YjI5NCAzXHVhYzFjIFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6Ijc4MjciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUcmFuc2l0aXZlIENsb3N1cmUiLCJkZXNjcmlwdGlvbiI6IjxwPkluIGFsbW9zdCBhbGwgSUNQQyB0cmFpbmluZ3MsIG9uZSBvZiB0aGUgYmFzaWMgaXRlbXMgdG8gYmUgdGF1Z2h0IChvciBldmVuIGJldHRlciwgYXNzdW1lZCkgaXMgaG93IHRvIGNvbXB1dGUgdGhlIHRyYW5zaXRpdmUgY2xvc3VyZSBvZiBhIGRpcmVjdGVkIGdyYXBoLiBTaW5jZSB0aGlzIGNvbmNlcHQgaXMgc28gZWxlbWVudGFyeSwgdGhlcmUgaXMgYSBwcm9mZXNzb3IgdGhhdCBzdWdnZXN0cyB0byBzb2x2ZSB0aGlzIHByb2JsZW0gdXNpbmcgV2Fyc2hhbGwmIzM5O3MgYWxnb3JpdGhtLiBBcyBvbmUgb2YgdGhlIGJvbnVzIHRhc2tzIG9mIHRoaXMgSUNQQywgd2Ugd291bGQgbGlrZSB0byBleGFtaW5lIHdoZXRoZXIgdGhlIHBhcnRpY2lwYW50cyBoYXZlIGluZGVlZCBtYXN0ZXJlZCB0aGlzIHRlY2huaXF1ZS48XC9wPlxyXG5cclxuPHA+R2l2ZW4gYSBkaXJlY3RlZCBncmFwaCBHID0gJmx0O1YsIEUmZ3Q7IHdpdGggTiA9IHxWfCB2ZXJ0aWNlcyAoMiAmbGU7IE4gJmxlOyAyLDUwMCkgYW5kIE0gPSB8RXwgZWRnZXMgKDEgJmxlOyBNICZsZTsgMTAsMDAwKSwgaXRzIHRyYW5zaXRpdmUgY2xvc3VyZSBpcyB0aGUgYmluYXJ5IHJlbGF0aW9uIFIgb24gViBzdWNoIHRoYXQgdHdvIHZlcnRpY2VzLCBBIGFuZCBCLCBhcmUgcmVsYXRlZCBpbiBSIGlmIHRoZXJlIGlzIGEgZGlyZWN0ZWQgcGF0aCBmcm9tIEEgdG8gQiwgd2hlcmUgYSBkaXJlY3RlZCBwYXRoIGlzIGEgc2VxdWVuY2Ugb2YgZWRnZXMgb2YgdGhlIGdyYXBoIEM8c3ViPjA8XC9zdWI+QzxzdWI+MTxcL3N1Yj4sIEM8c3ViPjE8XC9zdWI+QzxzdWI+MjxcL3N1Yj4sIC4uLiwgQzxzdWI+Sy0xPFwvc3ViPkM8c3ViPks8XC9zdWI+IHN1Y2ggdGhhdCBBID0gQzxzdWI+MDxcL3N1Yj4gYW5kIEIgPSBDPHN1Yj5LPFwvc3ViPi4gWW91ciB0YXNrIGlzIHRvIGNvbXB1dGUgUi48XC9wPlxyXG5cclxuPHA+QmVjYXVzZSBSIG1pZ2h0IGJlIHZlcnkgbGFyZ2UsIHdlXHUyMDFmdmUgZGVjaWRlZCB0byBzaW1wbGlmeSB0aGUgb3V0cHV0LiBDYWxjdWxhdGUgdGhlIG51bWJlciBvZiBvcmRlcmVkIHBhaXJzIG9mIChYLFkpIHdoZXJlIFggaXMgbm90IGVxdWFsIHRvIFkgc3VjaCB0aGF0IHRoZXJlIGlzIGEgcGF0aCBmcm9tIHZlcnRleCBYIHRvIHZlcnRleCBZIGluIGdyYXBoIEcuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhbiBpbnRlZ2VyIFQgKFQgJmxlOyAxMCksIGRlbm90aW5nIHRoZSBudW1iZXIgb2YgdGVzdGNhc2VzLiBUaGUgZm9sbG93aW5nIGxpbmVzIGRlc2NyaWJlIGVhY2ggdGVzdCBjYXNlIG9mIHRoZSBmb2xsb3dpbmcgZm9ybWF0LjxcL3A+XHJcblxyXG48cD5UaGUgZmlyc3QgbGluZSBvZiBhIHRlc3RjYXNlIGNvbnNpc3RzIG9mIHR3byBpbnRlZ2VycyBOIGFuZCBNLiBFYWNoIG9mIHRoZSBmb2xsb3dpbmcgTSBsaW5lcyBjb250YWlucyAyIGludGVnZXJzLCBBIGFuZCBCLCBkZW5vdGluZyB0aGF0IHRoZXJlIGlzIGEgZGlyZWN0ZWQgZWRnZSBmcm9tIEEgdG8gQi4gVGhlIHZlcnRpY2VzIGFyZSBudW1iZXJlZCBmcm9tIDEgdG8gTiwgYW5kIHRoZXJlIHdpbGwgYmUgbm8gcmVwZWF0ZWQgZWRnZXMgd2l0aGluIGEgZGVzY3JpcHRpb24gb2YgYSBncmFwaC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBjYXNlLCBvdXRwdXQgYW4gaW50ZWdlciBkZW5vdGluZyB0aGUgbnVtYmVyIG9mIG9yZGVyZWQgcGFpcnMgb2YgKFgsWSkgd2hlcmUgWCBpcyBub3QgZXF1YWwgdG8gWSBzdWNoIHRoYXQgdGhlcmUgaXMgYSBwYXRoIGZyb20gdmVydGV4IFggdG8gdmVydGV4IFkuPFwvcD5cclxuIiwiaGludCI6IjxwPkV4cGxhbmF0aW9uIGZvciB0aGUgMXN0IHNhbXBsZSBpbnB1dC48XC9wPlxyXG5cclxuPHA+VGhlIGJpbmFyeSByZWxhdGlvbiBSIGlzOjxcL3A+XHJcblxyXG48cHJlPlxyXG4wIDEgMVxyXG4wIDAgMVxyXG4wIDAgMDxcL3ByZT5cclxuXHJcbjxwPlRoZXJlIGFyZSAzIG9yZGVyZWQgcGFpcnMgb2YgKFgsWSkgc3VjaCB0aGF0IFI8c3ViPlgsWTxcL3N1Yj4gaXMgdHJ1ZS48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Asia Pacific > Indonesia > Jakarta > ACM-ICPC Regional Jakarta 2010 F번

  • 문제를 번역한 사람: Hibbah