如果某个无向连通图的任意一条边至多只出现在一条简单回路（simple cycle）里，我们就称这张图为仙人图（cactus）。所谓简单回路就是指在图上不重复经过任何一个顶点的回路。

举例来说，上面的第一个例子是一张仙人图，而第二个不是——注意到它有三条简单回路：（4，3，2，1，6，5，4）、（7，8，9，10，2，3，7）以及（4，3，7，8，9，10，2，1，6，5，4），而（2，3）同时出现在前两个的简单回路里。另外，第三张图也不是仙人图，因为它并不是连通图。显然，仙人图上的每条边，或者是这张仙人图的桥（bridge），或者在且仅在一个简单回路里，两者必居其一。定义在图上两点之间的距离为这两点之间最短路径的距离。定义一个图的直径为这张图相距最远的两个点的距离。现在我们假定仙人图的每条边的权值都是1，你的任务是求出给定的仙人图的直径。

输入的第一行包括两个整数n和m（1≤n≤50000以及0≤m≤10000）。其中n代表顶点个数，我们约定图中的顶点将从1到n编号。接下来一共有m行。代表m条路径。每行的开始有一个整数k（2≤k≤1000），代表在这条路径上的顶点个数。接下来是k个1到n之间的整数，分别对应了一个顶点，相邻的顶点表示存在一条连接这两个顶点的边。一条路径上可能通过一个顶点好几次，比如对于第一个样例，第一条路径从3经过8，又从8返回到了3，但是我们保证所有的边都会出现在某条路径上，而且不会重复出现在两条路径上，或者在一条路径上出现两次。

只需输出一个数，这个数表示仙人图的直径长度。

对第一个样例的说明：如图，6号点和12号点的最短路径长度为8，所以这张图的直径为8。

【注意】使用Pascal语言的选手请注意：你的程序在处理大数据的时候可能会出现栈溢出。如果需要调整栈空间的大小，可以在程序的开头填加一句：{$M 5000000}，其中5000000即指代栈空间的大小，请根据自己的程序选择适当的数值。

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>#include<set>using namespace std;#define PROB "cactus"#define MAXN 100010#define MAXV MAXN#define MAXE MAXV * 2#define INF 0x3f3f3f3fstruct edge{        int x,y,id;}e[MAXE];int n,m;int prv[MAXN];struct Edge{        int sp,np,val,id;        Edge *next;}E[MAXE],*V[MAXV];int tope;int dfn[MAXN],dfstime=0;int ans=0;void addedge(int x,int y,int id,int z=1){        E[++tope].np=y;        E[tope].id=id;        E[tope].sp=x;        E[tope].val=z;        E[tope].next=V[x];        V[x]=&E[tope];}int len[MAXN];int arr[MAXN];int seq[MAXN];int vis[MAXN];void solve(int rt,int now){        int tota=0;        int x,i;        x=now;        while (x!=rt)        {                arr[tota++]=len[x];                x=prv[x];        }        arr[tota++]=0;        for (i=0;i<tota;i++)                arr[i+tota]=arr[i];        x=0;        seq[0]=0;        int tail=0,head=0;        for (i=1;i<tota*2;i++)        {                while (i-seq[head]>tota/2)head++;                ans=max(ans,arr[seq[head]]+(i-seq[head])+arr[i]);                while (tail>=head && arr[seq[tail]] + (i-seq[tail]) <=arr[i])tail--;                seq[++tail]=i;        }}int low[MAXN];bool inc[MAXN];vector<int> ptr[MAXN];void dfs(int now,int pnt=-1){        low[now]=dfn[now]=++dfstime;        Edge *ne;        vis[now]=1;        int x=-1,y=-1;        int st=-1,rt;        for (ne=V[now];ne;ne=ne->next)        {                if (ne->np==prv[now])continue;                if (vis[ne->np]==1)                {                        ptr[ne->np].push_back(now);                        low[now]=min(low[now],dfn[ne->np]);                }else if (!vis[ne->np])                {                        prv[ne->np]=now;                        dfs(ne->np,now);                        low[now]=min(low[now],low[ne->np]);                }        }        for (int i=0;i<ptr[now].size();i++)        {                st=ptr[now][i],rt=now;                int sizc=1;                x=st;                inc[x]=true;                while (x!=rt)                {                        x=prv[x];                        inc[x]=true;                        sizc++;                }                x=st;                int d=1;                int t=0;                while (x!=rt)                {                        t=max(t,min(d,sizc-d)+len[x]);                        d++;                        x=prv[x];                }                ans=max(ans,t+len[rt]);                len[rt]=max(len[rt],t);                solve(rt,st);        }        x=y=0;        if (!inc[now])        {                for (ne=V[now];ne;ne=ne->next)                {                        if (dfn[ne->np]<dfn[now])continue;                        if (y<len[ne->np]+1)                        {                                y=len[ne->np]+1;                                if (x<y)swap(x,y);                        }                }        }        if (low[now]==dfn[now])        {                if (prv[now])ans=max(ans,len[now]+1+len[prv[now]]);                if (prv[now])len[prv[now]]=max(len[prv[now]],len[now]+1);        }        ans=max(ans,x+y);        vis[now]=2;}int deg[MAXN];void work(){        int i,x,y;        for (i=0;i<m;i++)        {                x=e[i].x;                y=e[i].y;                addedge(x,y,i);                addedge(y,x,i);                deg[x]++;                deg[y]++;        }        int core=0;        for (i=1;i<=n;i++)        {                if (deg[i]==1)core=i;                if (!core && deg[i]%2==1)core=i;        }        if (!core)core=1;        dfs(core,core);}set<pair<int,int> > S;int main(){        //freopen(PROB".in","r",stdin);        //freopen(PROB".out","w",stdout);        int l;        scanf("%d%d",&n,&l);        int i,j,k;        int x,y,z;        for (i=0;i<l;i++)        {                scanf("%d",&x);                scanf("%d",&y);                for (j=1;j<x;j++)                {                        scanf("%d",&z);                        e[m].x=y;                        e[m].y=z;                        m++;                        y=z;                }        }        for (i=0;i<m;i++)        {                if (e[i].x>e[i].y)swap(e[i].x,e[i].y);                if (e[i].x==e[i].y || S.find(make_pair(e[i].x,e[i].y))!=S.end())                {                        i--;m--;                        continue;                }else                {                        S.insert(make_pair(e[i].x,e[i].y));                }                e[i].id=i;        }        work();        printf("%d\n",ans);}