#include <cstdio>
#include <iostream>
#include <string.h>
using namespace std;

int m,n,q,r,dp[5005],a[5005][5005],ans=0;
int dfs(int x)
{
	if(dp[x]) return dp[x];
	for(int i=1;i<=m;i++){
		if(x==i) continue;
		else if(a[i][x])
		dp[x]=max(dp[x],dfs(i)+1);
	}
	return dp[x];
}

int main()
{
	cin>>m>>n;
	memset(a,0,sizeof(a));
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i++){
		cin>>q>>r;
		a[q][r]=1;
	}
	for(int i=1;i<=m;i++){
		ans=max(dfs(i),ans);
	}
	cout<<(ans+1)%80112002<<endl;;
	return 0;
}