#include <bits/stdc++.h>
using namespace std;
#define int long long

#define dbg(x...) \
do { \
std::cout << #x << " -> "; \
err(x); \
} while (0)

void err() {
	std::cout << std::endl;
}

template<class T, class... Ts>
void err(T arg, Ts &... args) {
	std::cout << fixed << setprecision(10) << arg << ' ';
	err(args...);
}

void GENSHEN_START() {
	int n,m;cin >> n >> m;
	vector <int> du(n + 5);
	vector <vector<pair<int,int>>> g(n + 5);
	for (int i = 1;i <= m;i++) {
		int u,v;cin >> u >> v;
		g[u].push_back({v,i});
		du[v]++;
	}
	queue <int> q;
	for (int i = 1;i <= n;i++) {
		if (du[i] == 0 && i != 1) {
			q.push(i);
		}
	}
	vector <int> vis(m + 5);
	while (!q.empty()) {
		auto now = q.front();q.pop();
		for (auto [v,p] : g[now]) {
			du[v]--;
			vis[p] = 1;
			if (du[v] == 0) q.push(v);
		}
	}
	vector <int> good(m + 5);
	vector <int> edge;
	int ans = 0;
	auto dfs = [&](auto self,int u) {
		if (u == n) {
			if (edge.empty()) return ;
			for (auto i : edge) good[i] = 1;
			ans++;
			edge.clear();
			return ;
		}	
		for (auto [v,p] : g[u]) {
			if (vis[p]) continue;
			if (!good[p]) edge.push_back(p);
			self(self,v);
		}
	};
	dfs(dfs,1);
	cout << ans;
}

signed main()
{
	ios::sync_with_stdio(false);cin.tie(nullptr);
	int T = 1;
	//cin >> T;
	while (T--) GENSHEN_START();
	return 0;
}