给一个有向图，有 $n$ 个点，$m$ 条边。然后选一条路径起点终点都为的路径出来，有一次机会可以沿某条边逆方向走，问最多有多少个点可以被经过？（一个点在路径中无论出现多少正整数次对答案的贡献均为 $1$ ）

$1\le n,m \le 10^6$

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100100;
int n,m;
int ans;
struct egde{
	int nxt,to;
}e[N*2];
int head[N],cnt;
int dfn[N],low[N],md,id[N],inst[N];
stack <int> st;

inline void add(int u,int v){
	e[++cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}

struct egded{
	int nxt,to;
}ed[N*2];
int headd[N],cntd;
int sized[N];

inline void addd(int u,int v){
	ed[++cntd].to=v;
	ed[cntd].nxt=headd[u];
	headd[u]=cntd;
}

void getdag(){
	for(int i=1;i<=n;i++){
		for(int j=head[i];j;j=e[j].nxt){
			int v=e[j].to;
			if(id[i]==id[v]) continue;
			addd(id[i],id[v]);
		}
	}
}

int dt;
void tarjan(int u){
	dfn[u]=low[u]=++dt;
	st.push(u);inst[u]=true;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}else if(inst[v]) low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		++md;
		while(st.size()){
			id[st.top()]=md,inst[st.top()]=false;
			sized[md]++;
			if(st.top()==u){
				st.pop();
				break;
			}
			st.pop();
		}
	}
}

int res0[N];
void dfs0(int u,int fa){
	res0[u]=max(res0[u],res0[fa]+sized[u]);
	ans=max(ans,res0[u]);
	for(int i=headd[u];i;i=ed[i].nxt){
		int v=ed[i].to;
		dfs0(v,u);
	}
	return;
}

int res1[N];
bool vis[N];
void dfs1(int u){
	vis[u]=true;
	for(int i=headd[u];i;i=ed[i].nxt){
		int v=ed[i].to;
		if(v==id[1]) res1[u]=max(res1[u],sized[u]);
		else{
			if(!vis[v]) dfs1(v);
			if(res1[v]>0) res1[u]=max(res1[u],sized[u]+res1[v]);
		}
	}
}

signed main(){
	for(int i=1;i<=100000;i++) res1[i]=res0[i]=-0x7fffffff;
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		add(a,b);
	} 
	for(int i=1;i<=n;i++){
		if(!dfn[i]) tarjan(i);
	}
	getdag();
	dfs0(id[1],0);
	for(int i=1;i<=md;i++){
		if(i!=id[1] and !vis[i]) dfs1(i);
	}
	for(int i=1;i<=md;i++){
		if(res1[i]<=0) continue;
		for(int j=headd[i];j;j=ed[j].nxt){
			int v=ed[j].to;
			ans=max(ans,res0[v]+res1[i]);
		}
	}
	cout<<ans;
}

本蒟蒻的思路：先 $tarjan$ 缩点，然后跑两次 $dp$ 分别求出从 $1$ 到每个点以及从每个点回到 $1$ 的最大权值，最后枚举每一条边作为逆向边得出答案