시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초 128 MB107191640.000%

문제

해시(hash)란 주어진 데이터를 하나의 수로 표현하는 것을 말한다. 예를 들어서 "1024"와 같은 문자열을 1024 라는 수로 생각하는 방법은 해시의 한 예이다. 또, 영단어에서 'a'부터 'z'까지를 1에서 26까지의 수로 생각하여 그 수들을 합한 것도 해시의 한 예이다. 이런 해시를 적용하면 "ab"와 같은 영단어는 3이라는 수가 되고, "ace"와 같은 영단어는 9라는 수가 된다.

당신은 그래프에 대해서 해시 함수를 하나 설계하였다. 당신이 설계한 해시 값은 그래프의 1번 정점에서 2번 정점까지 가는 모든 경로들의 경로 값의 최소공배수로 정의한다. 경로 값은 경로 상에 있는 모든 간선의 가중치들의 최대공약수로 정의한다. 물론 경로에서는 같은 정점이 두 번 이상 나와서는 안 된다.

예를 들어 위와 같은 그래프를 보자. 위의 그래프에서 1번 정점에서 2번 정점까지 가는 경로는 1-4-2, 1-3-2의 두 개가 있다. 각 경로의 경로 값은 2(16, 6의 최대공약수), 3(3, 9의 최대공약수)이 되고, 따라서 해시 값은 6(2, 3의 최소공배수)이 된다.

하나의 그래프가 주어졌을 때, 그 그래프의 해시 값(위에서 설계한 해시 함수를 이용하여 계산한)을 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 그래프의 정점의 개수 N(2 ≤ N ≤ 30)이 주어진다. 다음 N개의 줄에는 N개의 음 아닌 정수로 대칭적인 인접 행렬이 주어진다. 0인 경우는 간선이 없을 때를 나타내며, 그 외의 간선의 가중치는 1이상 5,000이하의 자연수이다.

출력

첫째 줄에 해시 값을 출력한다. 이 값은 10진수로 1000자리를 넘지 않는다.

예제 입력 1

4
0 0 3 16
0 0 9 6
3 9 0 0
16 6 0 0

예제 출력 1

6
W3sicHJvYmxlbV9pZCI6IjIzMjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkZjhcdWI3OThcdWQ1MDRcdWM3NTggXHVkNTc0XHVjMmRjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1NzRcdWMyZGMoaGFzaClcdWI3ODAgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1Yjk3YyBcdWQ1NThcdWIwOThcdWM3NTggXHVjMjE4XHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NDQgXHViOWQwXHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0XHVjMTFjICZxdW90OzEwMjQmcXVvdDtcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCAxMDI0IFx1Yjc3Y1x1YjI5NCBcdWMyMThcdWI4NWMgXHVjMGRkXHVhYzAxXHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWQ1NzRcdWMyZGNcdWM3NTggXHVkNTVjIFx1YzYwOFx1Yzc3NFx1YjJlNC4gXHViNjEwLCBcdWM2MDFcdWIyZThcdWM1YjRcdWM1ZDBcdWMxMWMgJiMzOTthJiMzOTtcdWJkODBcdWQxMzAgJiMzOTt6JiMzOTtcdWFlNGNcdWM5YzBcdWI5N2MgMVx1YzVkMFx1YzExYyAyNlx1YWU0Y1x1YzljMFx1Yzc1OCBcdWMyMThcdWI4NWMgXHVjMGRkXHVhYzAxXHVkNTU4XHVjNWVjIFx1YWRmOCBcdWMyMThcdWI0ZTRcdWM3NDQgXHVkNTY5XHVkNTVjIFx1YWM4M1x1YjNjNCBcdWQ1NzRcdWMyZGNcdWM3NTggXHVkNTVjIFx1YzYwOFx1Yzc3NFx1YjJlNC4gXHVjNzc0XHViN2YwIFx1ZDU3NFx1YzJkY1x1Yjk3YyBcdWM4MDFcdWM2YTlcdWQ1NThcdWJhNzQgJnF1b3Q7YWImcXVvdDtcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YzYwMVx1YjJlOFx1YzViNFx1YjI5NCAzXHVjNzc0XHViNzdjXHViMjk0IFx1YzIxOFx1YWMwMCBcdWI0MThcdWFjZTAsICZxdW90O2FjZSZxdW90O1x1YzY0MCBcdWFjMTlcdWM3NDAgXHVjNjAxXHViMmU4XHVjNWI0XHViMjk0IDlcdWI3N2NcdWIyOTQgXHVjMjE4XHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmY5XHVjMmUwXHVjNzQwIFx1YWRmOFx1Yjc5OFx1ZDUwNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVkNTc0XHVjMmRjIFx1ZDU2OFx1YzIxOFx1Yjk3YyBcdWQ1NThcdWIwOTggXHVjMTI0XHVhY2M0XHVkNTU4XHVjNjAwXHViMmU0LiBcdWIyZjlcdWMyZTBcdWM3NzQgXHVjMTI0XHVhY2M0XHVkNTVjIFx1ZDU3NFx1YzJkYyBcdWFjMTJcdWM3NDAgXHVhZGY4XHViNzk4XHVkNTA0XHVjNzU4IDFcdWJjODggXHVjODE1XHVjODEwXHVjNWQwXHVjMTFjIDJcdWJjODggXHVjODE1XHVjODEwXHVhZTRjXHVjOWMwIFx1YWMwMFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVhY2JkXHViODVjXHViNGU0XHVjNzU4IFx1YWNiZFx1Yjg1YyBcdWFjMTJcdWM3NTggXHVjZDVjXHVjMThjXHVhY2Y1XHViYzMwXHVjMjE4XHViODVjIFx1YzgxNVx1Yzc1OFx1ZDU1Y1x1YjJlNC4gXHVhY2JkXHViODVjIFx1YWMxMlx1Yzc0MCBcdWFjYmRcdWI4NWMgXHVjMGMxXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVhYzA0XHVjMTIwXHVjNzU4IFx1YWMwMFx1YzkxMVx1Y2U1OFx1YjRlNFx1Yzc1OCBcdWNkNWNcdWIzMDBcdWFjZjVcdWM1N2RcdWMyMThcdWI4NWMgXHVjODE1XHVjNzU4XHVkNTVjXHViMmU0LiBcdWJiM2NcdWI4NjAgXHVhY2JkXHViODVjXHVjNWQwXHVjMTFjXHViMjk0IFx1YWMxOVx1Yzc0MCBcdWM4MTVcdWM4MTBcdWM3NzQgXHViNDUwIFx1YmM4OCBcdWM3NzRcdWMwYzEgXHViMDk4XHVjNjQwXHVjMTFjXHViMjk0IFx1YzU0OCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgaGVpZ2h0PVwiMjM5XCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMTFcL2hhLlBOR1wiIHdpZHRoPVwiMjY4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgXHVjNzA0XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWFkZjhcdWI3OThcdWQ1MDRcdWI5N2MgXHViY2Y0XHVjNzkwLiBcdWM3MDRcdWM3NTggXHVhZGY4XHViNzk4XHVkNTA0XHVjNWQwXHVjMTFjIDFcdWJjODggXHVjODE1XHVjODEwXHVjNWQwXHVjMTFjIDJcdWJjODggXHVjODE1XHVjODEwXHVhZTRjXHVjOWMwIFx1YWMwMFx1YjI5NCBcdWFjYmRcdWI4NWNcdWIyOTQgMS00LTIsIDEtMy0yXHVjNzU4IFx1YjQ1MCBcdWFjMWNcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVhY2JkXHViODVjXHVjNzU4IFx1YWNiZFx1Yjg1YyBcdWFjMTJcdWM3NDAgMigxNiwgNlx1Yzc1OCBcdWNkNWNcdWIzMDBcdWFjZjVcdWM1N2RcdWMyMTgpLCAzKDMsIDlcdWM3NTggXHVjZDVjXHViMzAwXHVhY2Y1XHVjNTdkXHVjMjE4KVx1Yzc3NCBcdWI0MThcdWFjZTAsIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWQ1NzRcdWMyZGMgXHVhYzEyXHVjNzQwIDYoMiwgM1x1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjZjVcdWJjMzBcdWMyMTgpXHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTU4XHViMDk4XHVjNzU4IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFkZjggXHVhZGY4XHViNzk4XHVkNTA0XHVjNzU4IFx1ZDU3NFx1YzJkYyBcdWFjMTIoXHVjNzA0XHVjNWQwXHVjMTFjIFx1YzEyNFx1YWNjNFx1ZDU1YyBcdWQ1NzRcdWMyZGMgXHVkNTY4XHVjMjE4XHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU1OFx1YzVlYyBcdWFjYzRcdWMwYjBcdWQ1NWMpXHVjNzQ0IFx1YWQ2Y1x1ZDU3NFx1YjBiNFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFkZjhcdWI3OThcdWQ1MDRcdWM3NTggXHVjODE1XHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCBOKDIgJmxlOyBOICZsZTsgMzApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IE5cdWFjMWNcdWM3NTggXHVjNzRjIFx1YzU0NFx1YjJjYyBcdWM4MTVcdWMyMThcdWI4NWMgXHViMzAwXHVjZTZkXHVjODAxXHVjNzc4IFx1Yzc3OFx1YzgxMSBcdWQ1ODlcdWI4MmNcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAwXHVjNzc4IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWFjMDRcdWMxMjBcdWM3NzQgXHVjNWM2XHVjNzQ0IFx1YjU0Y1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWJhNzAsIFx1YWRmOCBcdWM2NzhcdWM3NTggXHVhYzA0XHVjMTIwXHVjNzU4IFx1YWMwMFx1YzkxMVx1Y2U1OFx1YjI5NCAxXHVjNzc0XHVjMGMxIDUsMDAwXHVjNzc0XHVkNTU4XHVjNzU4IFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDU3NFx1YzJkYyBcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3NzQgXHVhYzEyXHVjNzQwIDEwXHVjOWM0XHVjMjE4XHViODVjIDEwMDBcdWM3OTBcdWI5YWNcdWI5N2MgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyMzI4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ293IE1hdGgiLCJkZXNjcmlwdGlvbiI6IjxwPlRha2luZyB0aGVpciBjdWUgZnJvbSB0aGUgYnVpbGRlcnMgb2YgdGhlIFVTQSYjMzk7cyBJbnRlcnN0YXRlIEhpZ2h3YXkgc3lzdGVtLCB0aGUgY293cyBoYXZlIGludHJvZHVjZWQgdGhlIEludGVycGFzdHVyZSBQYXRoIG51bWJlcmluZyBzeXN0ZW0uIFRoZXkgaGF2ZSBhbHJlYWR5IG51bWJlcmVkIHRoZSBOICgyICZsdDs9IE4gJmx0Oz0gMzApIHBhc3R1cmVzIHdpdGggdGhlIGludGVnZXJzIDEuLk4gYW5kIG5vdyBhcmUgbnVtYmVyaW5nIGVhY2ggcGF0aCBiZXR3ZWVuIHR3byBwYXN0dXJlcyB3aXRoIGl0cyBvd24gZGlzdGluY3QgSW50ZXJwYXN0dXJlIFBhdGggbnVtYmVyIGluIHRoZSByYW5nZSAxLi41MDAwICZuYnNwOyhlLmcuLCBJLTkgYW5kIEktMTYpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5JbiBhbiBleGFtcGxlIEludGVycGFzdHVyZSBQYXRoIG1hcCwgZm91ciBwYXN0dXJlcyBudW1iZXJlZCAxLCAyLCAzLCBhbmQgNCBhcmUgY29ubmVjdGVkIGJ5IEludGVycGFzdHVyZSBQYXRocyBJLTMsIEktNiwgSS05LCBhbmQgSS0xNjombmJzcDs8XC9wPlxyXG5cclxuPHByZT5cclxuICAgICAgICAgICAgICAgICAgNC0tJmx0OyBJLTYmZ3Q7LS0yXHJcblxyXG4gICAgICAgICAgICAgICAgIFwvICAgICAgICAgXC9cclxuXHJcbiAgICAgICAgICAgICAmbHQ7IEktMTYmZ3Q7ICAgICAmbHQ7IEktOSZndDsgICBcclxuXHJcbiAgICAgICAgICAgICAgIFwvICAgICAgICAgXC9cclxuXHJcbiAgICAgICAgICAgICAgMS0tJmx0OyBJLTMmZ3Q7LS0zICBcclxuPFwvcHJlPlxyXG5cclxuPHA+QmVzc2llIGxpa2VzIHRvIHdhbGsgZnJvbSBwYXN0dXJlIDEgdG8gcGFzdHVyZSAyIG9uIHRoZSBuaWZ0eSBuZXcgSW50ZXJwYXN0dXJlIHN5c3RlbS4gRHVyaW5nIGVhY2ggd2Fsaywgc2hlIG5ldmVyIHZpc2l0cyB0aGUgc2FtZSBwYXN0dXJlIHR3aWNlLCBzbyBwb3NzaWJsZSB3YWxrcyBvbiB0aGUgc2FtcGxlIG1hcCBhYm92ZSBhcmUgMS00LTIgYW5kIDEtMy0yLiZuYnNwOzxcL3A+XHJcblxyXG48cD5PdmVyIHRoZSB5ZWFycywgQmVzc2llIGhhcyBkZXZlbG9wZWQgYW4gYW1hemluZyBtYXRoZW1hdGljYWwgc2tpbGwgdGhhdCBzaGUgbGlrZXMgdG8gZXhlcmNpc2UuIER1cmluZyBlYWNoIHdhbGssIHNoZSBlbmpveXMgZmluZGluZyB0aGUgZ3JlYXRlc3QgY29tbW9uIGZhY3RvciAoR0NGKSBvZiB0aGUgSW50ZXJwYXN0dXJlIFBhdGhzIHRoYXQgc2hlIHRyYXZlcnNlcy4gRm9yIGluc3RhbmNlLCB0aGUgd2FsayBkZXNpZ25hdGVkIDEtNC0yIHRvdWNoZXMgSS0xNiBhbmQgSS02IHdoaWNoIGhhdmUgdGhlIGdyZWF0ZXN0IGNvbW1vbiBmYWN0b3Igb2YgMiAoc2luY2UgMiBwcm9wZXJseSBkaXZpZGVzIGludG8gMTYgYW5kIDYgYnV0IG5vIGxhcmdlciBpbnRlZ2VyIGRvZXMpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BcyBzaGUgd2Fsa3MgdGhlIHBhc3R1cmVzIGRheSBhZnRlciBkYXksIHNoZSB0YWtlcyBhbGwgdGhlIHBvc3NpYmxlIHJvdXRlcyBmcm9tIHBhc3R1cmUgMSB0byBwYXN0dXJlIDIgYW5kIHJlbWVtYmVycyBlYWNoIG9mIHRoZSBHQ0ZzLiBBZnRlciBzaGUgaGFzIHRha2VuIGV2ZXJ5IHBvc3NpYmxlIHdhbGsgb25jZSwgc2hlIGNvbXB1dGVzIHRoZSBsZWFzdCBjb21tb24gbXVsdGlwbGUgKExDTSkgb2YgYWxsIHRoZSBHQ0ZzLiBGb3IgdGhpcyBleGFtcGxlLCB0aGUgdHdvIEdDRiB2YWx1ZXMgYXJlIDIgYW5kIDMgKEdDRig2LDE2KT0yIGFuZCBHQ0YoMyw5KT0zKSwgc28gdGhlIExDTSBpcyA2LiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3IgbGFyZ2UgbmV0d29ya3Mgb2YgcGF0aHMsIEJlc3NpZSBtaWdodCBnZXQgdGlyZWQgb2YgYWxsIHRoZSB3YWxraW5nLCBidXQgc2hlIHJlYWxseSB3YW50cyB0byBrbm93IHRoZSBMQ00gZm9yIGV2ZXJ5IG1hcC4gQ2FsY3VsYXRlIHRoYXQgbnVtYmVyIGZvciBoZXIuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogTiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5MaW5lcyAyLi5OKzE6IFRoZXNlIE4gbGluZXMgcmVwcmVzZW50IHRoZSBzeW1tZXRyaWMgSW50ZXJwYXN0dXJlIFBhdGggY29ubmVjdGl2aXR5IG1hdHJpeCBvZiB0aGUgcGFzdHVyZXMuIExpbmUgTCBzaG93cyB0aGUgY29ubmVjdGl2aXR5IGJldHdlZW4gcGFzdHVyZSBMLTEgYW5kIHRoZSBvdGhlciBwYXN0dXJlcyB3aXRoIGl0cyBOIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2Vycy4gVGhlIGZpcnN0IGludGVnZXIgb24gZWFjaCBsaW5lIGlzIHRoZSBJbnRlcnBhc3R1cmUgUGF0aCBudW1iZXIgdGhhdCBjb25uZWN0cyBwYXN0dXJlIEwtMSBhbmQgYW5kIHBhc3R1cmUgMTsgdGhlIHNlY29uZCBpbnRlZ2VyIGlzIHRoZSBJUCBudW1iZXIgY29ubmVjdGluZyBwYXN0dXJlIEwtMSBhbmQgcGFzdHVyZSAyOyBldGMuIElmIHBhc3R1cmUgQSBjb25uZWN0cyB0byBwYXN0dXJlIEIsIHRoZW4gcGFzdHVyZSBCIGNvbm5lY3RzIHRvIFBhc3R1cmUgQS4gV2hlbiBubyBJbnRlcnBhc3R1cmUgUGF0aCBpcyBhdmFpbGFibGUsIHRoZSBpbnRlZ2VyIGlzIDAuJm5ic3A7PFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5BIHNpbmdsZSBsaW5lIHdpdGggYSBzaW5nbGUgaW50ZWdlciB0aGF0IGlzIHRoZSBMQ00gb2YgdGhlIEdDRnMgb2YgYWxsIHRoZSBwb3NzaWJsZSB3YWxrcyBmcm9tIHBhc3R1cmUgMSB0byBwYXN0dXJlIDIuIEl0IGlzIGd1YXJhbnRlZWQgdGhhdCB0aGUgYW5zd2VyIHdpbGwgY29udGFpbiAxMDAwJm5ic3A7b3IgZmV3ZXIgZGlnaXRzLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > USA Computing Olympiad > 2002-2003 Season > USACO February 2003 Contest > Green Division 1번

  • 문제의 오타를 찾은 사람: klimmek55