30pts。

#include<bits/stdc++.h>
using namespace std;
int ig[114514], dfn[114514], low[114514], col[114514], vl[114514];
int n, m, a1, a2, cnt, ign, ans;
bool vis[114514];
vector<int> G[114514], NG[114514];
stack<int> s;
queue<int> q;
long long dis[114514];
int in[114514];
void tarjan(int u){
	dfn[u] = low[u] = ++cnt;
	s.push(u);
	vis[u] = 1;
	for (auto &v : G[u]){
		if (!dfn[v]){
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}else if (vis[v])
			low[u] = min(low[u], dfn[v]);
	}
	if (dfn[u] == low[u]){
		while (!s.empty()){
			int v = s.top();
			s.pop();
			vis[v] = 0;
			col[v] = u;
			vl[u]++;
			if (u == v)
				break;
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++){
		int u, v;
		cin >> u >> v;
		G[u].push_back(v);
	}
	for (int i = 1; i <= n; i++)
		if (!dfn[i])
			tarjan(i);
	for (int i = 1; i <= n; i++)
		for (auto v : G[i]){
			if (col[i] == col[v])
				continue;
			NG[col[i]].push_back(col[v]);
			ig[col[i]] = ig[col[v]] = 1;
			in[col[v]]++;
	//		cout << col[i] << "->" << col[v] << "\n";
		}
	for (int i = 1; i <= n; i++)
		if (col[i] == i && !ig[i])
			ig[i] = 1;
	for (int i = 1; i <= n; i++)
		if (ig[i])
			ign++;
	if (vl[1] != 1 || col[1] != 1){
		cout << "inf";
		return 0;
	}
	q.push(1);
	dis[1] = 1;
	while (!q.empty()){
		int u = q.front();
		q.pop();
	//	cout << u << "\n";
		for (auto v : NG[u]){
			in[v]--;
			if (!in[v])
				q.push(v);
		//	cout << v << " " << in[v] << "\n";
			if (dis[v] == -1)
				continue;
			if (dis[u] == -1 || vl[v] > 1){
				dis[v] = -1;
		//		cout << u << " " << dis[u] << " " << v << " " << dis[v] << "\n";
				continue;
			}
			dis[v] = (dis[v] + dis[u]) % 1000000000;
		//	cout << u << " " << dis[u] << " " << v << " " << dis[v] << "\n";
		}
	}
	if (dis[2] == -1)
		cout << "inf";
	else
		cout << dis[2];
}