coci06c3p5.cpp

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

// ----------- define --------------
#define int long long
#define vi vector<int>
#define ii pair<int,int>
#define fi first
#define sc second
#define mp make_pair
#define pqueue priority_queue
#define popcnt __builtin_popcount
#define getBit(x, k) ((x >> k) & 1)
#define all(x) (x).begin(),(x).end()
// ---------------------------------

const int N = 10005;
const int mod = 1e9;

int vst[N], ist[N], cnt[N], cdd[N];
vector<int> rev[N];

int flag = 0;

int cal(int i) {
  if (ist[i]) {
    if (i != 2) cdd[i] = 1;
    return 0;
  }
  if (vst[i]) return cnt[i];
  vst[i] = ist[i] = 1;
  if (i == 1) cnt[i] = 1;
  for (auto &j : rev[i]) {
    cnt[i] += cal(j);
    if (cnt[i] >= mod) {
      cnt[i] -= mod;
      flag = 1;
    }
  }
  if (cdd[i] && cnt[i]) {
    cout << "inf" << '\n';
    exit(0);
  }
  ist[i] = 0;
  return cnt[i];
}

void Main() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    rev[v].push_back(u);
  }
  int ans = cal(2);
  if (!flag) cout << ans << '\n';
  else cout << setw(9) << setfill('0') << ans << '\n';
}

signed main() {
#ifdef _DEBUG
  // freopen("in" , "r", stdin );
  cerr << "- ---- -- ----- <3\n";
#endif
  cin.tie(0)->sync_with_stdio(0);
  int T = 1;
  // cin >> T;
  while (T--) Main();
}