#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int INF = 1e9 + 7;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
if (!(cin >> n >> m)) return 0;
vector<vector<int>> adj(n);
vector<vector<int>> adjr(n);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adjr[v].push_back(u);
}
// 1. BFS from 0 to all nodes in the original graph.
// This gives us the cost to reach 0 if the troll flips the graph while we are at cave u.
// Do NOT skip cave n-1, because after a flip, n-1 is just a normal cave!
vector<int> dist0(n, INF);
queue<int> q;
dist0[0] = 0;
q.push(0);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (dist0[v] == INF) {
dist0[v] = dist0[u] + 1;
q.push(v);
}
}
}
// 2. Min-Max Dijkstra starting from the exit N-1 backwards.
vector<int> res(n, INF);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
res[n - 1] = 0;
pq.push({0, n - 1});
while (!pq.empty()) {
int d = pq.top().first;
int u = pq.top().second;
pq.pop();
// Standard Dijkstra optimization to skip outdated distance pairs
if (d > res[u]) continue;
for (int v : adjr[u]) {
// If I am at v, and decide to move to u:
// Troll can flip NOW: Cost is dist0[v]
// Troll waits: Cost is 1 move (to u) + whatever the worst-case cost from u is (res[u])
// The troll chooses the max of these.
// We want to minimize our time, so we only update if this path is better than our current res[v].
int weight = max(dist0[v], res[u] + 1);
if (weight < res[v]) {
res[v] = weight;
pq.push({res[v], v});
}
}
}
// 3. Output the result for caves 0 to N-2
for (int i = 0; i < n - 1; i++) {
cout << res[i] << (i == n - 2 ? "" : " ");
}
cout << "\n";
return 0;
}
