시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 35 10 10 38.462%

문제

해시(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
W3sicHJvYmxlbV9pZCI6IjIzMjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkZjhcdWI3OThcdWQ1MDRcdWM3NTggXHVkNTc0XHVjMmRjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1NzRcdWMyZGMoaGFzaClcdWI3ODAgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1Yjk3YyBcdWQ1NThcdWIwOThcdWM3NTggXHVjMjE4XHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NDQgXHViOWQwXHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0XHVjMTFjICZxdW90OzEwMjQmcXVvdDtcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCAxMDI0IFx1Yjc3Y1x1YjI5NCBcdWMyMThcdWI4NWMgXHVjMGRkXHVhYzAxXHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWQ1NzRcdWMyZGNcdWM3NTggXHVkNTVjIFx1YzYwOFx1Yzc3NFx1YjJlNC4gXHViNjEwLCBcdWM2MDFcdWIyZThcdWM1YjRcdWM1ZDBcdWMxMWMgJ2EnXHViZDgwXHVkMTMwICd6J1x1YWU0Y1x1YzljMFx1Yjk3YyAxXHVjNWQwXHVjMTFjIDI2XHVhZTRjXHVjOWMwXHVjNzU4IFx1YzIxOFx1Yjg1YyBcdWMwZGRcdWFjMDFcdWQ1NThcdWM1ZWMgXHVhZGY4IFx1YzIxOFx1YjRlNFx1Yzc0NCBcdWQ1NjlcdWQ1NWMgXHVhYzgzXHViM2M0IFx1ZDU3NFx1YzJkY1x1Yzc1OCBcdWQ1NWMgXHVjNjA4XHVjNzc0XHViMmU0LiBcdWM3NzRcdWI3ZjAgXHVkNTc0XHVjMmRjXHViOTdjIFx1YzgwMVx1YzZhOVx1ZDU1OFx1YmE3NCAmcXVvdDthYiZxdW90O1x1YzY0MCBcdWFjMTlcdWM3NDAgXHVjNjAxXHViMmU4XHVjNWI0XHViMjk0IDNcdWM3NzRcdWI3N2NcdWIyOTQgXHVjMjE4XHVhYzAwIFx1YjQxOFx1YWNlMCwgJnF1b3Q7YWNlJnF1b3Q7XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWM2MDFcdWIyZThcdWM1YjRcdWIyOTQgOVx1Yjc3Y1x1YjI5NCBcdWMyMThcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcbjxwPlx1YjJmOVx1YzJlMFx1Yzc0MCBcdWFkZjhcdWI3OThcdWQ1MDRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1ZDU3NFx1YzJkYyBcdWQ1NjhcdWMyMThcdWI5N2MgXHVkNTU4XHViMDk4IFx1YzEyNFx1YWNjNFx1ZDU1OFx1YzYwMFx1YjJlNC4gXHViMmY5XHVjMmUwXHVjNzc0IFx1YzEyNFx1YWNjNFx1ZDU1YyBcdWQ1NzRcdWMyZGMgXHVhYzEyXHVjNzQwIFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc1OCAxXHViYzg4IFx1YzgxNVx1YzgxMFx1YzVkMFx1YzExYyAyXHViYzg4IFx1YzgxNVx1YzgxMFx1YWU0Y1x1YzljMCBcdWFjMDBcdWIyOTQgXHViYWE4XHViNGUwIFx1YWNiZFx1Yjg1Y1x1YjRlNFx1Yzc1OCBcdWFjYmRcdWI4NWMgXHVhYzEyXHVjNzU4IFx1Y2Q1Y1x1YzE4Y1x1YWNmNVx1YmMzMFx1YzIxOFx1Yjg1YyBcdWM4MTVcdWM3NThcdWQ1NWNcdWIyZTQuIFx1YWNiZFx1Yjg1YyBcdWFjMTJcdWM3NDAgXHVhY2JkXHViODVjIFx1YzBjMVx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYWE4XHViNGUwIFx1YWMwNFx1YzEyMFx1Yzc1OCBcdWFjMDBcdWM5MTFcdWNlNThcdWI0ZTRcdWM3NTggXHVjZDVjXHViMzAwXHVhY2Y1XHVjNTdkXHVjMjE4XHViODVjIFx1YzgxNVx1Yzc1OFx1ZDU1Y1x1YjJlNC4gXHViYjNjXHViODYwIFx1YWNiZFx1Yjg1Y1x1YzVkMFx1YzExY1x1YjI5NCBcdWFjMTlcdWM3NDAgXHVjODE1XHVjODEwXHVjNzc0IFx1YjQ1MCBcdWJjODggXHVjNzc0XHVjMGMxIFx1YjA5OFx1YzY0MFx1YzExY1x1YjI5NCBcdWM1NDggXHViNDFjXHViMmU0LjxcL3A+XHJcbjxwPjxpbWcgd2lkdGg9XCIyNjhcIiBoZWlnaHQ9XCIyMzlcIiBhbHQ9XCJcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTAxMVwvaGEuUE5HXCIgXC8+PFwvcD5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBcdWM3MDRcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yjk3YyBcdWJjZjRcdWM3OTAuIFx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI3OThcdWQ1MDRcdWM1ZDBcdWMxMWMgMVx1YmM4OCBcdWM4MTVcdWM4MTBcdWM1ZDBcdWMxMWMgMlx1YmM4OCBcdWM4MTVcdWM4MTBcdWFlNGNcdWM5YzAgXHVhYzAwXHViMjk0IFx1YWNiZFx1Yjg1Y1x1YjI5NCAxLTQtMiwgMS0zLTJcdWM3NTggXHViNDUwIFx1YWMxY1x1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWFjYmRcdWI4NWNcdWM3NTggXHVhY2JkXHViODVjIFx1YWMxMlx1Yzc0MCAyKDE2LCA2XHVjNzU4IFx1Y2Q1Y1x1YjMwMFx1YWNmNVx1YzU3ZFx1YzIxOCksIDMoMywgOVx1Yzc1OCBcdWNkNWNcdWIzMDBcdWFjZjVcdWM1N2RcdWMyMTgpXHVjNzc0IFx1YjQxOFx1YWNlMCwgXHViNTMwXHViNzdjXHVjMTFjIFx1ZDU3NFx1YzJkYyBcdWFjMTJcdWM3NDAgNigyLCAzXHVjNzU4IFx1Y2Q1Y1x1YzE4Y1x1YWNmNVx1YmMzMFx1YzIxOClcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcbjxwPlx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWFkZjhcdWI3OThcdWQ1MDRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhZGY4IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc1OCBcdWQ1NzRcdWMyZGMgXHVhYzEyKFx1YzcwNFx1YzVkMFx1YzExYyBcdWMxMjRcdWFjYzRcdWQ1NWMgXHVkNTc0XHVjMmRjIFx1ZDU2OFx1YzIxOFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NThcdWM1ZWMgXHVhY2M0XHVjMGIwXHVkNTVjKVx1Yzc0NCBcdWFkNmNcdWQ1NzRcdWIwYjRcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFkZjhcdWI3OThcdWQ1MDRcdWM3NTggXHVjODE1XHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCBOKDImbGU7TiZsZTszMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWM3NGMgXHVjNTQ0XHViMmNjIFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWIzMDBcdWNlNmRcdWM4MDFcdWM3NzggXHVjNzc4XHVjODExIFx1ZDU4OVx1YjgyY1x1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIDBcdWM3NzggXHVhY2JkXHVjNmIwXHViMjk0IFx1YWMwNFx1YzEyMFx1Yzc3NCBcdWM1YzZcdWM3NDQgXHViNTRjXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YmE3MCwgXHVhZGY4IFx1YzY3OFx1Yzc1OCBcdWFjMDRcdWMxMjBcdWM3NTggXHVhYzAwXHVjOTExXHVjZTU4XHViMjk0IDFcdWM3NzRcdWMwYzEgNSwwMDBcdWM3NzRcdWQ1NThcdWM3NTggXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+Iiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQ1NzRcdWMyZGMgXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YWMxMlx1Yzc0MCAxMFx1YzljNFx1YzIxOFx1Yjg1YyAxMDAwXHVjNzkwXHViOWFjXHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyMzI4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ293IE1hdGgiLCJkZXNjcmlwdGlvbiI6IjxwPlRha2luZyB0aGVpciBjdWUgZnJvbSB0aGUgYnVpbGRlcnMgb2YgdGhlIFVTQSYjMzk7cyBJbnRlcnN0YXRlIEhpZ2h3YXkgc3lzdGVtLCB0aGUgY293cyBoYXZlIGludHJvZHVjZWQgdGhlIEludGVycGFzdHVyZSBQYXRoIG51bWJlcmluZyBzeXN0ZW0uIFRoZXkgaGF2ZSBhbHJlYWR5IG51bWJlcmVkIHRoZSBOICgyICZsdDs9IE4gJmx0Oz0gMzApIHBhc3R1cmVzIHdpdGggdGhlIGludGVnZXJzIDEuLk4gYW5kIG5vdyBhcmUgbnVtYmVyaW5nIGVhY2ggcGF0aCBiZXR3ZWVuIHR3byBwYXN0dXJlcyB3aXRoIGl0cyBvd24gZGlzdGluY3QgSW50ZXJwYXN0dXJlIFBhdGggbnVtYmVyIGluIHRoZSByYW5nZSAxLi41MDAwICZuYnNwOyhlLmcuLCBJLTkgYW5kIEktMTYpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5JbiBhbiBleGFtcGxlIEludGVycGFzdHVyZSBQYXRoIG1hcCwgZm91ciBwYXN0dXJlcyBudW1iZXJlZCAxLCAyLCAzLCBhbmQgNCBhcmUgY29ubmVjdGVkIGJ5IEludGVycGFzdHVyZSBQYXRocyBJLTMsIEktNiwgSS05LCBhbmQgSS0xNjombmJzcDs8XC9wPlxyXG5cclxuPHByZT5cclxuICAgICAgICAgICAgICAgICAgNC0tJmx0OyBJLTYmZ3Q7LS0yXHJcblxyXG4gICAgICAgICAgICAgICAgIFwvICAgICAgICAgXC9cclxuXHJcbiAgICAgICAgICAgICAmbHQ7IEktMTYmZ3Q7ICAgICAmbHQ7IEktOSZndDsgICBcclxuXHJcbiAgICAgICAgICAgICAgIFwvICAgICAgICAgXC9cclxuXHJcbiAgICAgICAgICAgICAgMS0tJmx0OyBJLTMmZ3Q7LS0zICBcclxuPFwvcHJlPlxyXG5cclxuPHA+QmVzc2llIGxpa2VzIHRvIHdhbGsgZnJvbSBwYXN0dXJlIDEgdG8gcGFzdHVyZSAyIG9uIHRoZSBuaWZ0eSBuZXcgSW50ZXJwYXN0dXJlIHN5c3RlbS4gRHVyaW5nIGVhY2ggd2Fsaywgc2hlIG5ldmVyIHZpc2l0cyB0aGUgc2FtZSBwYXN0dXJlIHR3aWNlLCBzbyBwb3NzaWJsZSB3YWxrcyBvbiB0aGUgc2FtcGxlIG1hcCBhYm92ZSBhcmUgMS00LTIgYW5kIDEtMy0yLiZuYnNwOzxcL3A+XHJcblxyXG48cD5PdmVyIHRoZSB5ZWFycywgQmVzc2llIGhhcyBkZXZlbG9wZWQgYW4gYW1hemluZyBtYXRoZW1hdGljYWwgc2tpbGwgdGhhdCBzaGUgbGlrZXMgdG8gZXhlcmNpc2UuIER1cmluZyBlYWNoIHdhbGssIHNoZSBlbmpveXMgZmluZGluZyB0aGUgZ3JlYXRlc3QgY29tbW9uIGZhY3RvciAoR0NGKSBvZiB0aGUgSW50ZXJwYXN0dXJlIFBhdGhzIHRoYXQgc2hlIHRyYXZlcnNlcy4gRm9yIGluc3RhbmNlLCB0aGUgd2FsayBkZXNpZ25hdGVkIDEtNC0yIHRvdWNoZXMgSS0xNiBhbmQgSS02IHdoaWNoIGhhdmUgdGhlIGdyZWF0ZXN0IGNvbW1vbiBmYWN0b3Igb2YgMiAoc2luY2UgMiBwcm9wZXJseSBkaXZpZGVzIGludG8gMTYgYW5kIDYgYnV0IG5vIGxhcmdlciBpbnRlZ2VyIGRvZXMpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BcyBzaGUgd2Fsa3MgdGhlIHBhc3R1cmVzIGRheSBhZnRlciBkYXksIHNoZSB0YWtlcyBhbGwgdGhlIHBvc3NpYmxlIHJvdXRlcyBmcm9tIHBhc3R1cmUgMSB0byBwYXN0dXJlIDIgYW5kIHJlbWVtYmVycyBlYWNoIG9mIHRoZSBHQ0ZzLiBBZnRlciBzaGUgaGFzIHRha2VuIGV2ZXJ5IHBvc3NpYmxlIHdhbGsgb25jZSwgc2hlIGNvbXB1dGVzIHRoZSBsZWFzdCBjb21tb24gbXVsdGlwbGUgKExDTSkgb2YgYWxsIHRoZSBHQ0ZzLiBGb3IgdGhpcyBleGFtcGxlLCB0aGUgdHdvIEdDRiB2YWx1ZXMgYXJlIDIgYW5kIDMgKEdDRig2LDE2KT0yIGFuZCBHQ0YoMyw5KT0zKSwgc28gdGhlIExDTSBpcyA2LiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3IgbGFyZ2UgbmV0d29ya3Mgb2YgcGF0aHMsIEJlc3NpZSBtaWdodCBnZXQgdGlyZWQgb2YgYWxsIHRoZSB3YWxraW5nLCBidXQgc2hlIHJlYWxseSB3YW50cyB0byBrbm93IHRoZSBMQ00gZm9yIGV2ZXJ5IG1hcC4gQ2FsY3VsYXRlIHRoYXQgbnVtYmVyIGZvciBoZXIuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogTiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5MaW5lcyAyLi5OKzE6IFRoZXNlIE4gbGluZXMgcmVwcmVzZW50IHRoZSBzeW1tZXRyaWMgSW50ZXJwYXN0dXJlIFBhdGggY29ubmVjdGl2aXR5IG1hdHJpeCBvZiB0aGUgcGFzdHVyZXMuIExpbmUgTCBzaG93cyB0aGUgY29ubmVjdGl2aXR5IGJldHdlZW4gcGFzdHVyZSBMLTEgYW5kIHRoZSBvdGhlciBwYXN0dXJlcyB3aXRoIGl0cyBOIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2Vycy4gVGhlIGZpcnN0IGludGVnZXIgb24gZWFjaCBsaW5lIGlzIHRoZSBJbnRlcnBhc3R1cmUgUGF0aCBudW1iZXIgdGhhdCBjb25uZWN0cyBwYXN0dXJlIEwtMSBhbmQgYW5kIHBhc3R1cmUgMTsgdGhlIHNlY29uZCBpbnRlZ2VyIGlzIHRoZSBJUCBudW1iZXIgY29ubmVjdGluZyBwYXN0dXJlIEwtMSBhbmQgcGFzdHVyZSAyOyBldGMuIElmIHBhc3R1cmUgQSBjb25uZWN0cyB0byBwYXN0dXJlIEIsIHRoZW4gcGFzdHVyZSBCIGNvbm5lY3RzIHRvIFBhc3R1cmUgQS4gV2hlbiBubyBJbnRlcnBhc3R1cmUgUGF0aCBpcyBhdmFpbGFibGUsIHRoZSBpbnRlZ2VyIGlzIDAuJm5ic3A7PFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5BIHNpbmdsZSBsaW5lIHdpdGggYSBzaW5nbGUgaW50ZWdlciB0aGF0IGlzIHRoZSBMQ00gb2YgdGhlIEdDRnMgb2YgYWxsIHRoZSBwb3NzaWJsZSB3YWxrcyBmcm9tIHBhc3R1cmUgMSB0byBwYXN0dXJlIDIuIEl0IGlzIGd1YXJhbnRlZWQgdGhhdCB0aGUgYW5zd2VyIHdpbGwgY29udGFpbiAxMDAwJm5ic3A7b3IgZmV3ZXIgZGlnaXRzLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=