시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 91 17 15 36.585%

문제

해시(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+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQ1NzRcdWMyZGMgXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YWMxMlx1Yzc0MCAxMFx1YzljNFx1YzIxOFx1Yjg1YyAxMDAwXHVjNzkwXHViOWFjXHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjIzMjgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDb3cgTWF0aCIsImRlc2NyaXB0aW9uIjoiPHA+VGFraW5nIHRoZWlyIGN1ZSBmcm9tIHRoZSBidWlsZGVycyBvZiB0aGUgVVNBJiMzOTtzIEludGVyc3RhdGUgSGlnaHdheSBzeXN0ZW0sIHRoZSBjb3dzIGhhdmUgaW50cm9kdWNlZCB0aGUgSW50ZXJwYXN0dXJlIFBhdGggbnVtYmVyaW5nIHN5c3RlbS4gVGhleSBoYXZlIGFscmVhZHkgbnVtYmVyZWQgdGhlIE4gKDIgJmx0Oz0gTiAmbHQ7PSAzMCkgcGFzdHVyZXMgd2l0aCB0aGUgaW50ZWdlcnMgMS4uTiBhbmQgbm93IGFyZSBudW1iZXJpbmcgZWFjaCBwYXRoIGJldHdlZW4gdHdvIHBhc3R1cmVzIHdpdGggaXRzIG93biBkaXN0aW5jdCBJbnRlcnBhc3R1cmUgUGF0aCBudW1iZXIgaW4gdGhlIHJhbmdlIDEuLjUwMDAgJm5ic3A7KGUuZy4sIEktOSBhbmQgSS0xNikuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkluIGFuIGV4YW1wbGUgSW50ZXJwYXN0dXJlIFBhdGggbWFwLCBmb3VyIHBhc3R1cmVzIG51bWJlcmVkIDEsIDIsIDMsIGFuZCA0IGFyZSBjb25uZWN0ZWQgYnkgSW50ZXJwYXN0dXJlIFBhdGhzIEktMywgSS02LCBJLTksIGFuZCBJLTE2OiZuYnNwOzxcL3A+XHJcblxyXG48cHJlPlxyXG4gICAgICAgICAgICAgICAgICA0LS0mbHQ7IEktNiZndDstLTJcclxuXHJcbiAgICAgICAgICAgICAgICAgXC8gICAgICAgICBcL1xyXG5cclxuICAgICAgICAgICAgICZsdDsgSS0xNiZndDsgICAgICZsdDsgSS05Jmd0OyAgIFxyXG5cclxuICAgICAgICAgICAgICAgXC8gICAgICAgICBcL1xyXG5cclxuICAgICAgICAgICAgICAxLS0mbHQ7IEktMyZndDstLTMgIFxyXG48XC9wcmU+XHJcblxyXG48cD5CZXNzaWUgbGlrZXMgdG8gd2FsayBmcm9tIHBhc3R1cmUgMSB0byBwYXN0dXJlIDIgb24gdGhlIG5pZnR5IG5ldyBJbnRlcnBhc3R1cmUgc3lzdGVtLiBEdXJpbmcgZWFjaCB3YWxrLCBzaGUgbmV2ZXIgdmlzaXRzIHRoZSBzYW1lIHBhc3R1cmUgdHdpY2UsIHNvIHBvc3NpYmxlIHdhbGtzIG9uIHRoZSBzYW1wbGUgbWFwIGFib3ZlIGFyZSAxLTQtMiBhbmQgMS0zLTIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk92ZXIgdGhlIHllYXJzLCBCZXNzaWUgaGFzIGRldmVsb3BlZCBhbiBhbWF6aW5nIG1hdGhlbWF0aWNhbCBza2lsbCB0aGF0IHNoZSBsaWtlcyB0byBleGVyY2lzZS4gRHVyaW5nIGVhY2ggd2Fsaywgc2hlIGVuam95cyBmaW5kaW5nIHRoZSBncmVhdGVzdCBjb21tb24gZmFjdG9yIChHQ0YpIG9mIHRoZSBJbnRlcnBhc3R1cmUgUGF0aHMgdGhhdCBzaGUgdHJhdmVyc2VzLiBGb3IgaW5zdGFuY2UsIHRoZSB3YWxrIGRlc2lnbmF0ZWQgMS00LTIgdG91Y2hlcyBJLTE2IGFuZCBJLTYgd2hpY2ggaGF2ZSB0aGUgZ3JlYXRlc3QgY29tbW9uIGZhY3RvciBvZiAyIChzaW5jZSAyIHByb3Blcmx5IGRpdmlkZXMgaW50byAxNiBhbmQgNiBidXQgbm8gbGFyZ2VyIGludGVnZXIgZG9lcykuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFzIHNoZSB3YWxrcyB0aGUgcGFzdHVyZXMgZGF5IGFmdGVyIGRheSwgc2hlIHRha2VzIGFsbCB0aGUgcG9zc2libGUgcm91dGVzIGZyb20gcGFzdHVyZSAxIHRvIHBhc3R1cmUgMiBhbmQgcmVtZW1iZXJzIGVhY2ggb2YgdGhlIEdDRnMuIEFmdGVyIHNoZSBoYXMgdGFrZW4gZXZlcnkgcG9zc2libGUgd2FsayBvbmNlLCBzaGUgY29tcHV0ZXMgdGhlIGxlYXN0IGNvbW1vbiBtdWx0aXBsZSAoTENNKSBvZiBhbGwgdGhlIEdDRnMuIEZvciB0aGlzIGV4YW1wbGUsIHRoZSB0d28gR0NGIHZhbHVlcyBhcmUgMiBhbmQgMyAoR0NGKDYsMTYpPTIgYW5kIEdDRigzLDkpPTMpLCBzbyB0aGUgTENNIGlzIDYuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciBsYXJnZSBuZXR3b3JrcyBvZiBwYXRocywgQmVzc2llIG1pZ2h0IGdldCB0aXJlZCBvZiBhbGwgdGhlIHdhbGtpbmcsIGJ1dCBzaGUgcmVhbGx5IHdhbnRzIHRvIGtub3cgdGhlIExDTSBmb3IgZXZlcnkgbWFwLiBDYWxjdWxhdGUgdGhhdCBudW1iZXIgZm9yIGhlci4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBOJm5ic3A7PFwvbGk+XHJcblx0PGxpPkxpbmVzIDIuLk4rMTogVGhlc2UgTiBsaW5lcyByZXByZXNlbnQgdGhlIHN5bW1ldHJpYyBJbnRlcnBhc3R1cmUgUGF0aCBjb25uZWN0aXZpdHkgbWF0cml4IG9mIHRoZSBwYXN0dXJlcy4gTGluZSBMIHNob3dzIHRoZSBjb25uZWN0aXZpdHkgYmV0d2VlbiBwYXN0dXJlIEwtMSBhbmQgdGhlIG90aGVyIHBhc3R1cmVzIHdpdGggaXRzIE4gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzLiBUaGUgZmlyc3QgaW50ZWdlciBvbiBlYWNoIGxpbmUgaXMgdGhlIEludGVycGFzdHVyZSBQYXRoIG51bWJlciB0aGF0IGNvbm5lY3RzIHBhc3R1cmUgTC0xIGFuZCBhbmQgcGFzdHVyZSAxOyB0aGUgc2Vjb25kIGludGVnZXIgaXMgdGhlIElQIG51bWJlciBjb25uZWN0aW5nIHBhc3R1cmUgTC0xIGFuZCBwYXN0dXJlIDI7IGV0Yy4gSWYgcGFzdHVyZSBBIGNvbm5lY3RzIHRvIHBhc3R1cmUgQiwgdGhlbiBwYXN0dXJlIEIgY29ubmVjdHMgdG8gUGFzdHVyZSBBLiBXaGVuIG5vIEludGVycGFzdHVyZSBQYXRoIGlzIGF2YWlsYWJsZSwgdGhlIGludGVnZXIgaXMgMC4mbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPkEgc2luZ2xlIGxpbmUgd2l0aCBhIHNpbmdsZSBpbnRlZ2VyIHRoYXQgaXMgdGhlIExDTSBvZiB0aGUgR0NGcyBvZiBhbGwgdGhlIHBvc3NpYmxlIHdhbGtzIGZyb20gcGFzdHVyZSAxIHRvIHBhc3R1cmUgMi4gSXQgaXMgZ3VhcmFudGVlZCB0aGF0IHRoZSBhbnN3ZXIgd2lsbCBjb250YWluIDEwMDAmbmJzcDtvciBmZXdlciBkaWdpdHMuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d