#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include<stack>
#include<bitset>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#include<unordered_map>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define aut(r,v) for(auto r:v)
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define pc() pop_back()
#define ull unsigned long long
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
#define endl '\n'
#define st stack<int>
#define vl vector<long long>
#define vi vector<int>
#define vb vector<bool>
#define vc vector<char>
#define pii pair<int,int>
#define vpii vector<pii>
#define vvi vector<vi>
#define vs vector<string>
#define mod 1000000007
#define un unordered_map<int,int>
#define mii map<int,int>
#define Sort(a) sort(all(a))
#define ED(a) Sort(a), a.erase(unique(all(a)), a.end())//removing all duplicates
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define Max(a) *max_element(all(a))
#define Min(a) *min_element(all(a))
#define MaxP(a) max_element(all(a)) - a.begin()
#define MinP(a) min_element(all(a)) - a.begin()
#define allUpper(a) transform(all(a), a.begin(), :: toupper)
#define allLower(a) transform(all(a), a.begin(), :: tolower)
#define rev(a) reverse(all(a))
#define ub(v,k) upper_bound(all(v), k) - v.begin()
#define lb(v,k) lower_bound(all(v), k) - v.begin()
#define adv(a,n) advance(auto it:a,n)
#define RSort(a) sort(a.rbegin(),a.rend()) //decending order
#define cnt(v,a) count(all(v),a)
#define bs(v,a) binary_search(all(v),a)
#define mmax(v) *max_element(all(v))
#define mmin(v) *min_element(all(v))
#define popcount(mask) __builtin_popcount(mask) // count set bit
#define popcountLL(mask) __builtin_popcountll(mask) // for long long
#define X real() // useful for working with #include <complex> for computational geometry
#define Y imag()
#define ll long long
#define ss second
#define ff first
#define trace1(x) cerr << #x << ": " << x << endl;
#define trace2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z) cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
//------------------------------CODE-----------------------------------------------------------------------
void bfs(int source, vvi& adj, vi& ans) {
vi vis(ans.size(), false);
vis[source] = true;
ans[source] = 0;
queue<int>q;
q.push(source);
while (!q.empty()) {
int cur = q.front();
q.pop();
for (auto it : adj[cur]) {
if (!vis[it]) {
q.push(it);
vis[it] = true;
ans[it] = ans[cur] + 1;
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int test;
test = 1;
//cin >> test;
//preprocess();
while (test--) {
int n;
cin >> n;
vvi v(n, vi(n));
rep(i, n) {
rep(j, n) {
cin >> v[i][j];
}
}
vvi ans(n, vi(n, -1));
vvi adj(n );
rep(i, n) {
rep(j, n) {
if (v[i][j] == 1) {
adj[j].push_back(i);
}
}
}
rep(i, n) {
bfs(i, adj, ans[i]);
}
rep(i, n) {
if (v[i][i] == 1) {
ans[i][i] = 1;
}
else {
ans[i][i] = INF;
rep(j, n) {
if (i == j)continue;
else {
if (ans[i][j] > 0 && ans[j][i] > 0) {
ans[i][i] = min(ans[i][i], ans[i][j] + ans[j][i]);
}
}
}
}
}
rep(i, n) {
if (ans[i][i] == INF)cout << "NO WAY" << endl;
else cout << ans[i][i] << endl;
}
}
};
I2luY2x1ZGUgPHN0cmluZz4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPG51bWVyaWM+CiNpbmNsdWRlIDxzZXQ+CiNpbmNsdWRlIDxtYXA+CiNpbmNsdWRlIDxxdWV1ZT4KCiNpbmNsdWRlPHN0YWNrPgojaW5jbHVkZTxiaXRzZXQ+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPHNzdHJlYW0+CiNpbmNsdWRlIDxjc3RkaW8+CiNpbmNsdWRlIDxjbWF0aD4KI2luY2x1ZGUgPGN0aW1lPgojaW5jbHVkZSA8Y3N0cmluZz4KI2luY2x1ZGUgPGNjdHlwZT4KI2luY2x1ZGUgPGNhc3NlcnQ+CiNpbmNsdWRlIDxsaW1pdHM+CiNpbmNsdWRlIDxmdW5jdGlvbmFsPgojaW5jbHVkZTx1bm9yZGVyZWRfbWFwPgoKI2RlZmluZSByZXAoaSxuKSBmb3IoaW50IChpKT0wOyhpKTwoaW50KShuKTsrKyhpKSkKCiNkZWZpbmUgcmV1KGksbCx1KSBmb3IoaW50IChpKT0oaW50KShsKTsoaSk8KGludCkodSk7KysoaSkpCiNkZWZpbmUgYXV0KHIsdikgZm9yKGF1dG8gcjp2KQoKI2RlZmluZSBlYWNoKGl0LG8pIGZvcihhdXQoaXQsIChvKS5iZWdpbigpKTsgaXQgIT0gKG8pLmVuZCgpOyArKyBpdCkKI2RlZmluZSBhbGwobykgKG8pLmJlZ2luKCksIChvKS5lbmQoKQojZGVmaW5lIHBiKHgpIHB1c2hfYmFjayh4KQojZGVmaW5lIHBjKCkgIHBvcF9iYWNrKCkKCiNkZWZpbmUgdWxsIHVuc2lnbmVkIGxvbmcgbG9uZwojZGVmaW5lIG1wKHgseSkgbWFrZV9wYWlyKCh4KSwoeSkpCiNkZWZpbmUgbXNldChtLHYpIG1lbXNldChtLHYsc2l6ZW9mKG0pKQoKI2RlZmluZSBJTkYgMHgzZjNmM2YzZgojZGVmaW5lIElORkwgMHgzZjNmM2YzZjNmM2YzZjNmTEwKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBlbmRsICdcbicKCiNkZWZpbmUgc3Qgc3RhY2s8aW50PgoKCgojZGVmaW5lIHZsIHZlY3Rvcjxsb25nIGxvbmc+CiNkZWZpbmUgdmkgdmVjdG9yPGludD4KI2RlZmluZSB2YiB2ZWN0b3I8Ym9vbD4KI2RlZmluZSB2YyB2ZWN0b3I8Y2hhcj4KI2RlZmluZSBwaWkgcGFpcjxpbnQsaW50PgojZGVmaW5lIHZwaWkgdmVjdG9yPHBpaT4KI2RlZmluZSB2dmkgdmVjdG9yPHZpPgojZGVmaW5lIHZzIHZlY3RvcjxzdHJpbmc+CgojZGVmaW5lIG1vZCAxMDAwMDAwMDA3CgojZGVmaW5lIHVuICB1bm9yZGVyZWRfbWFwPGludCxpbnQ+CiNkZWZpbmUgbWlpIG1hcDxpbnQsaW50PgoKI2RlZmluZSBTb3J0KGEpIHNvcnQoYWxsKGEpKQojZGVmaW5lIEVEKGEpIFNvcnQoYSksIGEuZXJhc2UodW5pcXVlKGFsbChhKSksIGEuZW5kKCkpLy9yZW1vdmluZyBhbGwgZHVwbGljYXRlcwoKI2RlZmluZSBtYXgzKGEsIGIsIGMpICAgbWF4KGEsIG1heChiLCBjKSkKI2RlZmluZSBtaW4zKGEsIGIsIGMpICAgbWluKGEsIG1pbihiLCBjKSkKI2RlZmluZSBNYXgoYSkgICAgICAgKm1heF9lbGVtZW50KGFsbChhKSkKI2RlZmluZSBNaW4oYSkgICAgICAgKm1pbl9lbGVtZW50KGFsbChhKSkKI2RlZmluZSBNYXhQKGEpICAgICAgIG1heF9lbGVtZW50KGFsbChhKSkgLSBhLmJlZ2luKCkKI2RlZmluZSBNaW5QKGEpICAgICAgICBtaW5fZWxlbWVudChhbGwoYSkpIC0gYS5iZWdpbigpCgojZGVmaW5lIGFsbFVwcGVyKGEpICAgICB0cmFuc2Zvcm0oYWxsKGEpLCBhLmJlZ2luKCksIDo6IHRvdXBwZXIpCiNkZWZpbmUgYWxsTG93ZXIoYSkgICAgIHRyYW5zZm9ybShhbGwoYSksIGEuYmVnaW4oKSwgOjogdG9sb3dlcikKCiNkZWZpbmUgcmV2KGEpICAgICAgICAgIHJldmVyc2UoYWxsKGEpKQojZGVmaW5lIHViKHYsaykgICAgICAgICAgdXBwZXJfYm91bmQoYWxsKHYpLCBrKSAtIHYuYmVnaW4oKQojZGVmaW5lIGxiKHYsaykgICAgICAgICAgbG93ZXJfYm91bmQoYWxsKHYpLCBrKSAtIHYuYmVnaW4oKQojZGVmaW5lIGFkdihhLG4pICAgICAgICBhZHZhbmNlKGF1dG8gaXQ6YSxuKQojZGVmaW5lIFJTb3J0KGEpICAgICAgICAgc29ydChhLnJiZWdpbigpLGEucmVuZCgpKSAvL2RlY2VuZGluZyBvcmRlcgojZGVmaW5lIGNudCh2LGEpICAgICAgICAgICAgIGNvdW50KGFsbCh2KSxhKQojZGVmaW5lIGJzKHYsYSkgICAgICAgICAgIGJpbmFyeV9zZWFyY2goYWxsKHYpLGEpCiNkZWZpbmUgbW1heCh2KSAgICAgICAgICAgKm1heF9lbGVtZW50KGFsbCh2KSkKI2RlZmluZSBtbWluKHYpICAgICAgICAgICAqbWluX2VsZW1lbnQoYWxsKHYpKQojZGVmaW5lIHBvcGNvdW50KG1hc2spICAgICAgICAgICAgICAgICAgICAgICBfX2J1aWx0aW5fcG9wY291bnQobWFzaykgLy8gY291bnQgc2V0IGJpdAojZGVmaW5lIHBvcGNvdW50TEwobWFzaykgICAgICAgICAgICAgICAgICAgICBfX2J1aWx0aW5fcG9wY291bnRsbChtYXNrKSAvLyBmb3IgbG9uZyBsb25nCiNkZWZpbmUgWCByZWFsKCkgLy8gdXNlZnVsIGZvciB3b3JraW5nIHdpdGggI2luY2x1ZGUgPGNvbXBsZXg+IGZvciBjb21wdXRhdGlvbmFsIGdlb21ldHJ5CiNkZWZpbmUgWSBpbWFnKCkKI2RlZmluZSBsbCBsb25nIGxvbmcKI2RlZmluZSBzcyBzZWNvbmQKI2RlZmluZSBmZiBmaXJzdAoKI2RlZmluZSB0cmFjZTEoeCkgICAgICAgICAgICAgICAgICAgICAgICAgICBjZXJyIDw8ICN4IDw8ICI6ICIgPDwgeCA8PCBlbmRsOwojZGVmaW5lIHRyYWNlMih4LCB5KSAgICAgICAgICAgICAgICAgICAgICAgIGNlcnIgPDwgI3ggPDwgIjogIiA8PCB4IDw8ICIgfCAiIDw8ICN5IDw8ICI6ICIgPDwgeSA8PCBlbmRsOwojZGVmaW5lIHRyYWNlMyh4LCB5LCB6KSAgICAgICAgICAgICAgICAgICAgIGNlcnIgPDwgI3ggPDwgIjogIiA8PCB4IDw8ICIgfCAiIDw8ICN5IDw8ICI6ICIgPDwgeSA8PCAiIHwgIiA8PCAjeiA8PCAiOiAiIDw8IHogPDwgZW5kbDsKI2RlZmluZSB0cmFjZTQoYSwgYiwgYywgZCkgICAgICAgICAgICAgICAgICBjZXJyIDw8ICNhIDw8ICI6ICIgPDwgYSA8PCAiIHwgIiA8PCAjYiA8PCAiOiAiIDw8IGIgPDwgIiB8ICIgPDwgI2MgPDwgIjogIiA8PCBjIDw8ICIgfCAiIDw8ICNkIDw8ICI6ICIgPDwgZCA8PCBlbmRsOwojZGVmaW5lIHRyYWNlNShhLCBiLCBjLCBkLCBlKSAgICAgICAgICAgICAgIGNlcnIgPDwgI2EgPDwgIjogIiA8PCBhIDw8ICIgfCAiIDw8ICNiIDw8ICI6ICIgPDwgYiA8PCAiIHwgIiA8PCAjYyA8PCAiOiAiIDw8IGMgPDwgIiB8ICIgPDwgI2QgPDwgIjogIiA8PCBkIDw8ICIgfCAiIDw8ICNlIDw8ICI6ICIgPDwgZSA8PCBlbmRsOwojZGVmaW5lIHRyYWNlNihhLCBiLCBjLCBkLCBlLCBmKSAgICAgICAgICAgIGNlcnIgPDwgI2EgPDwgIjogIiA8PCBhIDw8ICIgfCAiIDw8ICNiIDw8ICI6ICIgPDwgYiA8PCAiIHwgIiA8PCAjYyA8PCAiOiAiIDw8IGMgPDwgIiB8ICIgPDwgI2QgPDwgIjogIiA8PCBkIDw8ICIgfCAiIDw8ICNlIDw8ICI6ICIgPDwgZSA8PCAiIHwgIiA8PCAjZiA8PCAiOiAiIDw8IGYgPDwgZW5kbDsKCi8vLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tQ09ERS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCnZvaWQgYmZzKGludCBzb3VyY2UsIHZ2aSYgYWRqLCB2aSYgYW5zKSB7CiAgICB2aSB2aXMoYW5zLnNpemUoKSwgZmFsc2UpOwogICAgdmlzW3NvdXJjZV0gPSB0cnVlOwogICAgYW5zW3NvdXJjZV0gPSAwOwogICAgcXVldWU8aW50PnE7CiAgICBxLnB1c2goc291cmNlKTsKICAgIHdoaWxlICghcS5lbXB0eSgpKSB7CiAgICAgICAgaW50IGN1ciA9IHEuZnJvbnQoKTsKICAgICAgICBxLnBvcCgpOwogICAgICAgIGZvciAoYXV0byBpdCA6IGFkaltjdXJdKSB7CiAgICAgICAgICAgIGlmICghdmlzW2l0XSkgewogICAgICAgICAgICAgICAgcS5wdXNoKGl0KTsKICAgICAgICAgICAgICAgIHZpc1tpdF0gPSB0cnVlOwogICAgICAgICAgICAgICAgYW5zW2l0XSA9IGFuc1tjdXJdICsgMTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KCn0KCgoKaW50IG1haW4oKSB7CiAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIGNpbi50aWUoTlVMTCk7CiAgICBjb3V0LnRpZShOVUxMKTsKICAgIGludCB0ZXN0OwogICAgdGVzdCA9IDE7CiAgICAvL2NpbiA+PiB0ZXN0OwogICAgLy9wcmVwcm9jZXNzKCk7CiAgICAKICAgIHdoaWxlICh0ZXN0LS0pIHsKICAgICAgICBpbnQgbjsKICAgICAgICBjaW4gPj4gbjsKICAgICAgICB2dmkgdihuLCB2aShuKSk7CiAgICAgICAgcmVwKGksIG4pIHsKICAgICAgICAgICAgcmVwKGosIG4pIHsKICAgICAgICAgICAgICAgIGNpbiA+PiB2W2ldW2pdOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIHZ2aSBhbnMobiwgdmkobiwgLTEpKTsKICAgICAgICB2dmkgYWRqKG4gKTsKICAgICAgICByZXAoaSwgbikgewogICAgICAgICAgICByZXAoaiwgbikgewogICAgICAgICAgICAgICAgaWYgKHZbaV1bal0gPT0gMSkgewogICAgICAgICAgICAgICAgICAgIGFkaltqXS5wdXNoX2JhY2soaSk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgcmVwKGksIG4pIHsKICAgICAgICAgICAgYmZzKGksIGFkaiwgYW5zW2ldKTsKICAgICAgICB9CgogICAgICAgIHJlcChpLCBuKSB7CiAgICAgICAgICAgIGlmICh2W2ldW2ldID09IDEpIHsKICAgICAgICAgICAgICAgIGFuc1tpXVtpXSA9IDE7CiAKICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UgewogICAgICAgICAgICAgICAgYW5zW2ldW2ldID0gSU5GOwogICAgICAgICAgICAgICAgcmVwKGosIG4pIHsKICAgICAgICAgICAgICAgICAgICBpZiAoaSA9PSBqKWNvbnRpbnVlOwogICAgICAgICAgICAgICAgICAgIGVsc2UgewogICAgICAgICAgICAgICAgICAgICAgICBpZiAoYW5zW2ldW2pdID4gMCAmJiBhbnNbal1baV0gPiAwKSB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBhbnNbaV1baV0gPSBtaW4oYW5zW2ldW2ldLCBhbnNbaV1bal0gKyBhbnNbal1baV0pOwogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIHJlcChpLCBuKSB7CiAgICAgICAgICAgIGlmIChhbnNbaV1baV0gPT0gSU5GKWNvdXQgPDwgIk5PIFdBWSIgPDwgZW5kbDsKICAgICAgICAgICAgZWxzZSBjb3V0IDw8IGFuc1tpXVtpXSA8PCBlbmRsOwogICAgICAgIH0KICAgICAgICAKICAgIH0KCgoKCn07