记录编号	370254	评测结果	AAAAAAAAAA
题目名称	[SHOI 2008] 仙人掌图	最终得分	100
用户昵称	Cydiater	是否通过	通过
代码语言	C++	运行时间	0.055 s
提交时间	2017-02-13 08:17:50	内存使用	9.47 MiB

//BZOJ 1023
//by Cydiater
//2017.2.12
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <map>
#include <cstring>
#include <string>
#include <iomanip>
#include <ctime>
#include <algorithm>
#include <cstdio>
#include <bitset>
#include <set>
#include <vector>
#include <complex>
using namespace std;
#define ll long long
#define up(i,j,n)	for(int i=j;i<=n;i++)
#define down(i,j,n)	for(int i=j;i>=n;i--)
#define cmax(a,b)	a=max(a,b)
#define cmin(a,b)	a=min(a,b)
#define Auto(i,node)	for(int i=LINK[node];i;i=e[i].next)
#define FILE		"bzoj_1023"
const int MAXN=2e5+5;
const int oo=0x3f3f3f3f;
inline int read(){
	char ch=getchar();int x=0,f=1;
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int N,M,LINK[MAXN],len=0,dfn[MAXN],low[MAXN],dfs_clock,stack[MAXN],top=0,dccs=0,f[MAXN],ans=0;
int q[MAXN],head,tail,arr[MAXN];
vector<int>DCC[MAXN];
struct edge{
	int y,next;
}e[MAXN];
namespace solution{
	inline void insert(int x,int y){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;}
	inline void Insert(int x,int y){insert(x,y);insert(y,x);}
	void Prepare(){
		N=read();M=read();
		while(M--){
			int T=read(),last=read(),now;
			while(--T){
				now=read();
				Insert(now,last);
				last=now;
			}
		}
		dccs=N;
	}
	void Tarjan(int node){
		dfn[node]=low[node]=++dfs_clock;
		stack[++top]=node;
		Auto(i,node)if(!dfn[e[i].y]){
			Tarjan(e[i].y);
			cmin(low[node],low[e[i].y]);
			if(low[e[i].y]>=dfn[node]){
				dccs++;int tmp;
				do{
					tmp=stack[top--];
					DCC[dccs].push_back(tmp);
				}while(tmp!=e[i].y);
				DCC[node].push_back(dccs);
			}
		}else cmin(low[node],dfn[e[i].y]);
	}
	void TreeDP(int node){
		f[node]=0;
		int siz=DCC[node].size();
		if(node>N){
			up(i,0,siz-1)TreeDP(DCC[node][i]);
			up(i,0,siz-1)arr[i]=f[DCC[node][i]];
			arr[siz]=0;
			up(i,siz+1,siz<<1)arr[i]=arr[i-siz-1];
			head=1;tail=0;
			up(i,0,(siz+1)/2-1){
				while(head<=tail&&arr[q[tail]]+q[tail]<arr[i]+i)tail--;
				q[++tail]=i;
			}
			int R=(siz+1)/2;
			up(L,0,siz-1){
				if(R!=siz){
					while(head<=tail&&arr[q[tail]]+q[tail]<arr[R]+R)tail--;
					q[++tail]=R;
				}
				if(q[head]==L)head++;
				if(head<=tail)cmax(ans,arr[L]+arr[q[head]]+q[head]-L);
				R++;
			}
			up(i,0,(siz+1)/2-1)cmax(f[node],f[DCC[node][i]]+i);
			up(i,(siz+1)/2,siz-1)cmax(f[node],f[DCC[node][i]]+siz-1-i);
		}else{
			int Max1=0,Max2=0;
			up(i,0,siz-1){
				TreeDP(DCC[node][i]);
				if(f[DCC[node][i]]+1>Max1){Max2=Max1;Max1=f[DCC[node][i]]+1;}
				else if(f[DCC[node][i]]+1>Max2)Max2=f[DCC[node][i]]+1;
			}
			cmax(ans,Max1+Max2);
			f[node]=Max1;
		}
	}
	void Solve(){
		Tarjan(1);
		TreeDP(1);
		cout<<ans<<endl;
	}
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	using namespace solution;
	Prepare();
	Solve();
	return 0;
}