感觉 $O(n)$ 空间 $O(n)$ 时间妥妥的，然而 $\texttt{MLE} \ and\ \texttt{TLE}$ 了一片

我很不理解。$\text{宇宙射线照射的100}$ $\%$ 是 $dfs$ 的问题

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#define rep(i, a, b) for (int i = (a); i <= (b); i ++ )
#define rop(i, a, b) for (int i = (a); i < (b); i ++ )
#define dep(i, a, b) for (int i = (a); i >= (b); i -- )
#define dop(i, a, b) for (int i = (a); i > (b); i -- )

using namespace std;

using LL = long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;

const int N = 100010, mod = 1e9;
int f[N], col[N], n, m;
bool st[N];
vector<int> e1[N], e2[N];

void dfs1(int u) {
	col[u] = 1;
	for (auto i : e1[u])
		if (!col[i])
			dfs1(i);
}
void dfs2(int u) {
	col[u] += 5;
	for (auto i : e2[u])
		if (col[i] < 5)
			dfs2(i);
}
int dfs3(int u) {
	for (auto i : e1[u]) {
		if (col[i] != 6) continue;
		if (st[i]) return true;
		st[i] = true;
		if (dfs3(i)) return true;
		st[i] = false;
	} return false;
}
int dfs4(int u) {
	if (f[u]) return f[u];
	if (u == 2) return 1;
	int sum = 0;
	for (auto i : e1[u])
		(sum += dfs4(i)) %= mod;
	return f[u] = sum;
}

int main() {
	scanf("%d%d", &n, &m);
	while (m -- ) {
		int a, b;
		scanf("%d%d", &a, &b);
		e1[a].push_back(b), e2[b].push_back(a);
	}
	dfs1(1), dfs2(2); // 在正反图上染色
	
	if (dfs3(1)) return puts("inf"), 0; // 判断是否有环
	printf("%d", dfs4(1)); // 记忆化搜索统计路径
	return 0;
}