#include <bits/stdc++.h> using namespace std; #define fio ios_base::sync_with_stdio(false); cin.tie(NULL); typedef long long int lli; int n; int a[2001][2001]; int ans[2001]; void initialize() { for(int i=1;i<=2000;i++) { ans[i]=1000000000; } } void bfs(int s) { int visited[2001]={0}; visited[s]=1; int level[2001]={0}; level[s]=0; int root[2001]={0}; root[s]=s; queue<int> q; q.push(s); while(!q.empty()) { int node=q.front(); q.pop(); for(int i=1;i<=n;i++) { if(a[node][i]==1) { if(visited[i]==false) { visited[i]=true; level[i]=level[node]+1; q.push(i); root[i]=node; } else if(i==s) { int val=abs(level[node]-level[i])+1; int x=node; while(1) { ans[x]=min(val,ans[x]); x=root[x]; if(x==s) { ans[x]=min(val,ans[x]); break; } } return; } } } } ans[s]=-1; } int main() { fio; initialize(); cin>>n; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) cin>>a[i][j]; } for(int i=1;i<=n;i++) { if(ans[i]==1000000000) { bfs(i); if(ans[i]!=-1) cout<<ans[i]<<endl; else cout<<"NO WAY"<<endl; } else { cout<<ans[i]<<endl; } } return 0; }