记录编号	154657	评测结果	AAAAAAAAAA
题目名称	[SHOI 2008] 仙人掌图	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.079 s
提交时间	2015-03-23 19:10:31	内存使用	3.63 MiB

/***********************************************************************/
/**********************By Asm.Def-Wu Jiaxin*****************************/
/***********************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <algorithm>
#include <cmath>
using namespace std;
#define SetFile(x) ( freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) )
#define getc() getchar() 
template<class T>inline void getd(T &x){
	char ch = getc();bool neg = false;
	while(!isdigit(ch) && ch != '-')ch = getc();
	if(ch == '-')ch = getc(), neg = true;
	x = ch - '0';
	while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
	if(neg)x = -x;
}
/***********************************************************************/
#include <vector>
#include <queue>
#define pb push_back
#define pf push_front
const int maxn = 50005;
struct Edge{
	int u, v, top, size;
	void init(int a, int b){u = a, v = b;}
}E[maxn * 3], *Eend = E;
vector<Edge*>adj[maxn];
Edge *Last[maxn];
int dep[maxn], Ans, F[maxn], Stack[maxn], *Top = Stack;
bool istop[maxn];
struct Info{int val, id;Info(int a,int b){val = a, id = b;}};

inline void RollDP(int size){
	int val[maxn<<1], N, i, mid = size >> 1, *it = val, Max = 0;
	deque<Info> Q;
	for(i = 0;i < size;++i)*it = F[Top[i]], Max = max(Max, min(i, size-i) + *(it++));
	for(i = 0;i < mid;++i)*(it++) = F[Top[i]];

	//for(i = 0;i < it - val;++i)printf("F[%d] = %d ", Top[i%size], val[i]);putchar('\n');

	N = it - val;
	Ans = max(Ans, *val);
	Q.pb(Info(*val, 0));
	for(i = 1;i < N;++i){
		if(Q.front().id + mid < i)Q.pop_front();
		Ans = max(Ans, Q.front().val + val[i] + i);
		Info tmp(val[i]-i, i);
		while(!Q.empty() && Q.back().val <= tmp.val)Q.pop_back();
		Q.push_back(tmp);
	}
	F[*Top] = Max;

	//printf("F[cur] = %d\n", F[*Top]);
}

void dfs(int cur){
	static bool vis[maxn];vis[cur] = true;
	vector<Edge*>::iterator it;
	for(it = adj[cur].begin();it != adj[cur].end();++it){
		Edge &e = **it;
		if(Last[cur] && e.v == Last[cur]->u)continue;
		if(vis[e.v]){
			if(dep[e.v] > dep[cur])continue;
			Edge *t = &e;
			int top = e.v, s = dep[cur] - dep[top] + 1;
			do{
				*(Top++) = t->v;
				t->top = top, t->size = s;
				t = Last[t->u];
			}while(t && t->v != top);
		}
		else{
			Last[e.v] = &e, dep[e.v] = dep[cur] + 1;

			//printf("%d->%d\n", e.u, e.v);

			dfs(e.v);
			if(!e.top){
				Ans = max(Ans, F[cur] + F[e.v] + 1);
				F[cur] = max(F[cur], F[e.v] + 1);
			}
			else if(e.top == cur){
				while(*(--Top) != cur);
				RollDP(e.size);
			}
		}
	}
}

inline void work(){
	int N, M, k, u, v;
	getd(N);getd(M);
	while(M--){
		getd(k);getd(v);
		while(--k){
			u = v;getd(v);
			Eend->init(u, v);adj[u].pb(Eend++);
			Eend->init(v, u);adj[v].pb(Eend++);
		}
	}
	dfs(1);

	//for(int i = 1;i <= N;++i)printf("F[%d] = %d\n", i, F[i]);
}



int main(){

#ifdef DEBUG
	freopen("test.txt", "r", stdin);
#elif !defined ONLINE_JUDGE
	SetFile(bzoj_1023);
#endif
	work();
	printf("%d\n", Ans);

#ifdef DEBUG
	printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}