#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 5;
vector<bool> vis(maxn, false);
vector<int> adj[maxn];
vector<int> radj[maxn];
vector<int> ans;
int n, m;
void dfs(int x){
if(vis[x] == 1) return;
vis[x] = 1;
for(int X: adj[x]){
if(!vis[X]) dfs(X);
}
ans.push_back(x);
}
signed main(){
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
radj[v].push_back(u);
}
vector<int> dist(maxn, 1e18);
queue<int> q;
dist[0] = 0;
q.push(0);
while(!q.empty()) {
int u = q.front();
q.pop();
for (int v: adj[u]) {
if(dist[v] == 1e18) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, n-1});
vector<int> dp(maxn, 1e18);
dp[n - 1] = 0;
while (!pq.empty()) {
int ff = pq.top().first;
int ss = pq.top().second;
pq.pop();
if (ff > dp[ss]) continue;
for (int u : radj[ss]) {
int X = max(dist[u], dp[ss] + 1);
if (X < dp[u]) {
dp[u] = X;
pq.push({dp[u], u});
}
}
}
for (int i = 0; i <n-1; i++) cout << dp[i] << ' ';
return 0;
}
