#include <bits/stdc++.h>

#define X first
#define Y second
#define PB push_back
#define x first
#define y second
#define pb push_back
#define all(a) begin(a),end(a)
#define sz(a) (int)(a).size()
#define rep(i,a,b) for (int i=a;i<(b);++i)

using namespace std;

typedef long long ll;
using pii=pair<int,int>;
typedef vector<int> vi;

const int N=2e5 + 2,MOD=1e9+7;
const char en='\n';
const ll LLINF=1ll<<60;

int n, m, d[N], d2[N];
vector<int> adj[N];
int bio[N];
unordered_map<ll, bool> seen;

ll h(int a, int b) {
	return (ll)a * (1e9 + 1) + b;
}

bool possible(ll K) {
	memset(bio, 0, sizeof bio);
	queue<int> bfs;
	bfs.push(0);
	d[0] = 0;
	bio[0] = 1;
	if (d2[0] > K) return false;
	while (!bfs.empty()) {
		int node = bfs.front(); bfs.pop();
		for (int x : adj[node]) {
			if (bio[x] || (ll)d[node] + 1 + d2[x] > K) continue;
			bio[x] = 1;
			d[x] = d[node] + 1;
			bfs.push(x);
		}
	}
	return bio[n - 1];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int u, v; cin >> u >> v, --u, --v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	queue<pair<pii, int>> bfs;
	bfs.push({{n - 1, -1}, 0});
	bio[n - 1] = 2;
	while (!bfs.empty()) {
		int node = bfs.front().X.X, par = bfs.front().X.Y;
		int dst = bfs.front().Y;
		bfs.pop();
		for (int x : adj[node]) {
			if (x == par || bio[x] > 1 || seen[h(node, x)]) continue;
			seen[h(node, x)] = 1;
			if (!bio[x]) {
				d[x] = dst + 1;
				bio[x] = 1;
				bfs.push({{x, node}, dst + 1});
			} else {
				d2[x] = dst + 1;
				bio[x] = 2;
				bfs.push({{x, node}, dst + 1});
			}
		}
	}
	
	int lo = 0, hi = 2 * (n + m);
	while (lo < hi) {
		int mid = (lo + hi) >> 1;
		if (possible(mid)) hi = mid;
		else lo = mid + 1;
	}
	
	cout << lo << "\n";
	
	return 0;
}