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

문제

크기가 n이고, 체커보드처럼 n×n개의 칸으로 나누어져 있는 정사각형이 있다. 1 ≤ x1, y1, x2, y2 ≤ n 을 만족하는 두 위치 (x1, y1)와 (x2, y2)가 독립이 되려면, 서로 다른 행과 열을 차지하고 있어야 한다. 즉, x1 ≠ x2, y1 ≠ y2가 되어야 한다.n개의 위치가 독립일 되려면, 모든 쌍이 독립이 되어야 한다. 즉, 서로 다른 n개의 위치를 독립이 되도록 고르는 방법의 수는 총 n!개이다.

정사각형의 각 칸에 숫자가 써있다. 이 정사각형이 동차 정사각형이 되려면, n개의 독립적인 위치에 써 있는 숫자의 합이 고르는 방법과 상관없이 항상 같아야 한다.

정사각형에 써 있는 숫자가 주어졌을 때, 동차 정사각형인지 아닌지를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 정사각형의 크기 n이 주어진다. (1 ≤ n ≤ 1000) 다음 n개 줄에는 n개의 숫자가 공백으로 구분되어서 주어진다. 각 숫자는 [-1000000, 1000000] 범위 내에 들어있다. 입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 동차 정사각형이라면 "homogeneous"를, 아니라면 "not homogeneous"를 출력한다.

예제 입력 1

2
1 2
3 4
3
1 3 4
8 6 -2
-3 4 0
0

예제 출력 1

homogeneous
not homogeneous
W3sicHJvYmxlbV9pZCI6IjY1MjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzZDlcdWNjMjggXHVjMjE4XHVjNWY0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQwNmNcdWFlMzBcdWFjMDAgblx1Yzc3NFx1YWNlMCwgXHVjY2I0XHVjZWU0XHViY2Y0XHViNGRjXHVjYzk4XHViN2ZjIG4mdGltZXM7blx1YWMxY1x1Yzc1OCBcdWNlNzhcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NzQgXHVjNzg4XHViMmU0LiAxICZsZTsgeDEsIHkxLCB4MiwgeTIgJmxlOyBuIFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHViNDUwIFx1YzcwNFx1Y2U1OCAoeDEsIHkxKVx1YzY0MCAoeDIsIHkyKVx1YWMwMCBcdWIzYzVcdWI5YmRcdWM3NzQgXHViNDE4XHViODI0XHViYTc0LCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1ZDU4OVx1YWNmYyBcdWM1ZjRcdWM3NDQgXHVjYzI4XHVjOWMwXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1Yzk4OSwgeDEgJm5lOyB4MiwgeTEgJm5lOyB5Mlx1YWMwMCBcdWI0MThcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0Lm5cdWFjMWNcdWM3NTggXHVjNzA0XHVjZTU4XHVhYzAwIFx1YjNjNVx1YjliZFx1Yzc3YyBcdWI0MThcdWI4MjRcdWJhNzQsIFx1YmFhOFx1YjRlMCBcdWMzMGRcdWM3NzQgXHViM2M1XHViOWJkXHVjNzc0IFx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1Yzk4OSwgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBuXHVhYzFjXHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWIzYzVcdWI5YmRcdWM3NzQgXHViNDE4XHViM2M0XHViODVkIFx1YWNlMFx1Yjk3NFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViMjk0IFx1Y2QxZCBuIVx1YWMxY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YWMwMSBcdWNlNzhcdWM1ZDAgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YzM2OFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc3NCBcdWIzZDlcdWNjMjggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0IFx1YjQxOFx1YjgyNFx1YmE3NCwgblx1YWMxY1x1Yzc1OCBcdWIzYzVcdWI5YmRcdWM4MDFcdWM3NzggXHVjNzA0XHVjZTU4XHVjNWQwIFx1YzM2OCBcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwXHVjNzU4IFx1ZDU2OVx1Yzc3NCBcdWFjZTBcdWI5NzRcdWIyOTQgXHViYzI5XHViYzk1XHVhY2ZjIFx1YzBjMVx1YWQwMFx1YzVjNlx1Yzc3NCBcdWQ1NmRcdWMwYzEgXHVhYzE5XHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNWQwIFx1YzM2OCBcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YjNkOVx1Y2MyOCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NzhcdWM5YzAgXHVjNTQ0XHViMmNjXHVjOWMwXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWQwNmNcdWFlMzAgblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgbiAmbGU7IDEwMDApIFx1YjJlNFx1Yzc0YyBuXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBuXHVhYzFjXHVjNzU4IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0XHVjMTFjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YzIyYlx1Yzc5MFx1YjI5NCBbLTEwMDAwMDAsIDEwMDAwMDBdIFx1YmM5NFx1YzcwNCBcdWIwYjRcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWIzZDlcdWNjMjggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0XHViNzdjXHViYTc0ICZxdW90O2hvbW9nZW5lb3VzJnF1b3Q7XHViOTdjLCBcdWM1NDRcdWIyYzhcdWI3N2NcdWJhNzQgJnF1b3Q7bm90IGhvbW9nZW5lb3VzJnF1b3Q7XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI2NTI1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSG9tb2dlbmVvdXMgc3F1YXJlcyIsImRlc2NyaXB0aW9uIjoiPHA+QXNzdW1lIHlvdSBoYXZlIGEgc3F1YXJlIG9mIHNpemUgbiB0aGF0IGlzIGRpdmlkZWQgaW50byBuJnRpbWVzO24gcG9zaXRpb25zIGp1c3QgYXMgYSBjaGVja2VyYm9hcmQuIFR3byBwb3NpdGlvbnMgKHgxLHkxKSBhbmQgKHgyLHkyKSwgd2hlcmUgMSAmbGU7IHgxLHkxLHgyLHkyICZsZTsgbiwgYXJlIGNhbGxlZCAmcXVvdDtpbmRlcGVuZGVudCZxdW90OyBpZiB0aGV5IG9jY3VweSBkaWZmZXJlbnQgcm93cyBhbmQgZGlmZmVyZW50IGNvbHVtbnMsIHRoYXQgaXMsIHgxJm5lO3gyIGFuZCB5MSZuZTt5Mi4gTW9yZSBnZW5lcmFsbHksIG4gcG9zaXRpb25zIGFyZSBjYWxsZWQgaW5kZXBlbmRlbnQgaWYgdGhleSBhcmUgcGFpcndpc2UgaW5kZXBlbmRlbnQuIEl0IGZvbGxvd3MgdGhhdCB0aGVyZSBhcmUgbiEgZGlmZmVyZW50IHdheXMgdG8gY2hvb3NlIG4gaW5kZXBlbmRlbnQgcG9zaXRpb25zLjxcL3A+XHJcblxyXG48cD5Bc3N1bWUgZnVydGhlciB0aGF0IGEgbnVtYmVyIGlzIHdyaXR0ZW4gaW4gZWFjaCBwb3NpdGlvbiBvZiBzdWNoIGFuIG4mdGltZXM7biBzcXVhcmUuIFRoaXMgc3F1YXJlIGlzIGNhbGxlZCAmcXVvdDtob21vZ2VuZW91cyZxdW90OyBpZiB0aGUgc3VtIG9mIHRoZSBudW1iZXJzIHdyaXR0ZW4gaW4gbiBpbmRlcGVuZGVudCBwb3NpdGlvbnMgaXMgdGhlIHNhbWUsIG5vIG1hdHRlciBob3cgdGhlIHBvc2l0aW9ucyBhcmUgY2hvc2VuLiBXcml0ZSBhIHByb2dyYW0gdG8gZGV0ZXJtaW5lIGlmIGEgZ2l2ZW4gc3F1YXJlIGlzIGhvbW9nZW5lb3VzITxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnRhaW5zIHNldmVyYWwgdGVzdCBjYXNlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZpcnN0IGxpbmUgb2YgZWFjaCB0ZXN0IGNhc2UgY29udGFpbnMgYW4gaW50ZWdlciBuICgxICZsZTsgbiAmbGU7IDEwMDApLiBFYWNoIG9mIHRoZSBuZXh0IG4gbGluZXMgY29udGFpbnMgbiBudW1iZXJzLCBzZXBhcmF0ZWQgYnkgZXhhY3RseSBvbmUgc3BhY2UgY2hhcmFjdGVyLiBFYWNoIG51bWJlciBpcyBhbiBpbnRlZ2VyIGZyb20gdGhlIGludGVydmFsIFstMTAwMDAwMCwxMDAwMDAwXS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGxhc3QgdGVzdCBjYXNlIGlzIGZvbGxvd2VkIGJ5IGEgemVyby48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2Ugb3V0cHV0IHdoZXRoZXIgdGhlIHNwZWNpZmllZCBzcXVhcmUgaXMgaG9tb2dlbmVvdXMgb3Igbm90LiBBZGhlcmUgdG8gdGhlIGZvcm1hdCBzaG93biBpbiB0aGUgc2FtcGxlIG91dHB1dDxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

채점

  • 제출한 후 다른 소스를 제출하려면 3초가 지나야 한다.