#include <bits/stdc++.h>
#define ll long long
#define R register
#define F(i,a,b) for(int i = (a);i<=(b);i++)
using namespace std;
inline int read(){R int x=0,t=1;R char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') t=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*t;}
const int N=3e5+10;
int n,m,a[N],ans,top,dfn[N],low[N],l=1,r=0,st[N],cnt,b[N],f1[N],f2[N],u_[N],v_[N],S[N],q[N];
vector<int> g[N],G[N],G_[N],g1,g2;
bool vis[N];
void tarjan(int u)
{
dfn[u]=low[u]=++top;
st[++r]=u;
vis[u]=1;
for(int i = 0;i<g[u].size();i++){
int v=g[u][i];
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]){
cnt++;
while(st[r]!=u){
vis[st[r]]=0;
// cout << cnt << '\n';
b[st[r]]=cnt;
S[cnt]++;
r--;
}
vis[u]=0;
//cout << cnt << '\n';
b[u]=cnt;
S[cnt]++;
r--;
}
return;
}
struct Node
{
int id,sum,wsr;
};
bool operator<(const Node&a,const Node&b)
{
return a.sum<b.sum;
}
//priority_queue<Node>q;
/*
inline void dij(int rt)//dij跑缩后的最长路
{
dis[rt][0]=S[rt];
q.push({rt,S[rt],0});
// vis[rt]=1;
for(;q.size();){
Node u=q.top();
q.pop();
// cout << u.id << " " << u.sum << " " << u.wsr << '\n';
///if(vis[u.id]) continue;
//vis[u.id]=1;
for(int i = 0;i<G_[u.id].size();i++){
int v=G_[u.id][i];
if(u.wsr==0){
if(dis[v][1]<dis[u.id][0]+S[v]){
dis[v][1]=dis[u.id][0]+S[v];
q.push({v,dis[v][1],1});
}
}
}
for(int i = 0;i<G[u.id].size();i++){
int v=G[u.id][i];
if(u.wsr!=0){
if(dis[v][1]<dis[u.id][1]+S[v]){
dis[v][1]=dis[u.id][1]+S[v];
q.push({v,dis[v][1],1});
}
}
else{
if(dis[v][0]<dis[u.id][0]+S[v]){
dis[v][0]=dis[u.id][0]+S[v];
q.push({v,dis[v][0],0});
}
if(dis[v][1]<dis[u.id][1]+S[v]){
dis[v][1]=dis[u.id][1]+S[v];
q.push({v,dis[v][1],1});
}
}
}
}
}*/
inline void add(int ui,int vi)//原图
{
g[ui].push_back(vi);
//g[vi].push_back(ui);
return;
}
inline void add1(int ui,int vi)//缩完点的图
{
G[ui].push_back(vi);
G_[vi].push_back(ui);
}
inline void solve()
{
n=read(),m=read();
F(i,1,m){
u_[i]=read(),v_[i]=read();
add(u_[i],v_[i]);
}
//dij(1);
for(int i=1;i<=n;i++) {
if(!dfn[i]){
tarjan(i);
}
}
// F(i,1,n) if(b[i]==0) b[i]=++cnt,S[cnt]=1;
// cout << l << " " << r << '\n';
// F(i,1,n) cout << b[i] << '\n';
// F(i,1,cnt)
// {
// cout << i << " " << S[i] << '\n';
// }
F(i,1,m){
int ui=u_[i],vi=v_[i];
if(b[ui]!=b[vi]){//两个不属于同一个强连通分量
//bdcdcout << ui << " " << vi << '\n';
//cout << b[ui] << " " << b[vi] << '\n';
//cout << "------------------------\n";
g1.push_back(ui);
g2.push_back(vi);
add1(ui,vi);
}
}
l=1,r=0;
q[++r]=b[1];
f1[b[1]]=0;
for(;l<=r;)
{
int u=q[l++];
for(int i = 0;i<G[u].size();i++){
int v=G[u][i];
f1[v]=max(f1[u]+S[v],f1[v]);
q[++r]=v;
}
}
l=1,r=0;
q[++r]=b[1];
f2[b[1]]=1;
for(;l<=r;)
{
int u=q[l++];
for(int i = 0;i<G_[u].size();i++){
int v=G_[u][i];
f2[v]=max(f2[v],f2[u]+S[v]);
q[++r]=v;
}
}
int maxn=S[b[1]];
for(int i = 0;i<g1.size();i++){
int ui=g1[i],vi=g2[i];
maxn=max(maxn,f1[ui]+f2[vi]);
maxn=max(maxn,f1[vi]+f2[ui]);
}
cout << maxn;
}
signed main()
{
solve();
return 0;
}
题面：
约翰有 n 块草场，编号 1 到 n，这些草场由若干条单行道相连。奶牛贝西是美味牧草的鉴赏家，她想到达尽可能多的草场去品尝牧草。
贝西总是从 1 号草场出发，最后回到 1 号草场。她想经过尽可能多的草场，贝西在通一个草场只吃一次草，所以一个草场可以经过多次。因为草场是单行道连接，这给贝西的品鉴工作带来了很大的不便，贝西想偷偷逆向行走一次，但最多只能有一次逆行。问，贝西最多能吃到多少个草场的牧草。
样例输入：
7 10
1 2
3 1
2 5
2 4
3 7
3 5
3 6
6 5
7 2
4 7
输出：
6