[USACO15JAN]Grass Cownoisseur G

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <vector> 
#include <queue> 
#include <cassert>
#define LL long long
#define uint unsigned int
using namespace std;
const int MAXN = 2e5 + 5;
#define Debug(x) cerr << #x << ' ' << x
#define hh cerr << endl
int n, m, col[MAXN], dfn[MAXN], tot, low[MAXN], s[MAXN], cnt, nk;
int edgex[MAXN], edgey[MAXN], maxx, dp[MAXN], siz[MAXN];
bool vis[MAXN];
vector <int> v[MAXN];
queue <int> que;
// dij 好像不能跑最大值
// 强连通+分层图+spfa（雾 
// 由于原图是个 dag，所以这个分层图也是个 dag，所以可以直接用拓扑排序 
// 其实这个 spfa 的复杂度和 top排序是一样的 / emm
void dfs(int x) {
	dfn[x] = ++ tot; low[x] = tot; s[++ cnt] = x;
	for(uint i = 0; i < v[x].size(); i ++) {
		int y = v[x][i];
		if(!dfn[y]) dfs(y), low[x] = min(low[x], low[y]);
		else if(!col[y]) low[x] = min(low[x], dfn[y]);
	}
	if(dfn[x] == low[x]) {
		nk ++; int t;
		do {
			t = s[cnt --]; col[t] = nk;
		} while(t != x);
	}
}
void spfa() {
	que.push(col[1]); vis[col[1]] = 1; dp[col[1]] = siz[col[1]];
	while(!que.empty()) {
		int t = que.front(); que.pop(); vis[t] = 0;
		for(uint i = 0; i < v[t].size(); i ++) {
			int y = v[t][i];
			if(dp[y] < dp[t] + siz[y]) {
				dp[y] = dp[t] + siz[y]; assert(siz[y] > 0);
				if(!vis[y]) vis[y] = 1, que.push(y);
			}
		}
	}
}
int main() {
	int x, y;
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i ++) {
		scanf("%d%d", &x, &y); v[x].push_back(y); edgex[i] = x; edgey[i] = y;
	}
	for(int i = 1; i <= n; i ++) if(!dfn[i]) dfs(i);
	for(int i = 1; i <= n; i ++) v[i].clear(), siz[col[i]] ++, siz[col[i] + nk] ++;
	for(int i = 1; i <= m; i ++) {
		if(col[edgex[i]] != col[edgey[i]]) {
			v[col[edgex[i]]].push_back(col[edgey[i]]);
			v[col[edgex[i]] + nk].push_back(col[edgey[i]] + nk);
			v[col[edgey[i]]].push_back(col[edgex[i]] + nk);
		}
	}
	spfa(); maxx = max(dp[col[1]], dp[col[1] + nk]);
	if(nk == 1) maxx += siz[col[1]]; // 特判 
	printf("%d", maxx - siz[col[1]]);
	return 0;
}