[BZOJ 1023] [SHOI 2008] 선인장 그림

#include
using namespace std;
const int MAXN = 100005;
template  void chkmax(T &x, T y) {x = max(x, y); }
template  void chkmin(T &x, T y) {x = min(x, y); } 
template  void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template  void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template  void writeln(T x) {
	write(x);
	puts("");
}
vector  a[MAXN], b[MAXN];
int n, m, oldn, ans;
int top, Stack[MAXN], len[MAXN];
int timer, dfn[MAXN], low[MAXN];
int dp[MAXN][2];
void dfs(int pos, int fa) {
	if (pos <= oldn) {
		for (unsigned i = 0; i < b[pos].size(); i++)
			if (b[pos][i] != fa) dfs(b[pos][i], pos);
	} else {
		int tmp = 0;
		for (unsigned i = 0; i < b[pos].size(); i++)
			if (b[pos][i] != fa) {
				int dest = b[pos][i];
				dfs(dest, pos);
				int tnp = b[pos].size() - 1 - i;
				chkmax(tmp, dp[dest][0] + min(tnp, len[pos] - tnp));
			}
		if (tmp > dp[fa][0]) {
			dp[fa][1] = dp[fa][0];
			dp[fa][0] = tmp;
		} else chkmax(dp[fa][1], tmp);
	}
}
void tarjan(int pos) {
	Stack[++top] = pos;
	dfn[pos] = low[pos] = ++timer;
	for (unsigned i = 0; i < a[pos].size(); i++)
		if (dfn[a[pos][i]] == 0) {
			tarjan(a[pos][i]);
			chkmin(low[pos], low[a[pos][i]]);
			if (low[a[pos][i]] >= dfn[pos]) {
				int tmp = 0, last = 0; n++;
				while (tmp != a[pos][i]) {
					last = tmp;
					tmp = Stack[top--];
					b[n].push_back(tmp);
					b[tmp].push_back(n);
					len[n]++;
				}
				b[n].push_back(pos);
				b[pos].push_back(n);
				len[n]++;
			}
		} else chkmin(low[pos], dfn[a[pos][i]]);
}
int main() {
	read(n), read(m), oldn = n;
	for (int i = 1; i <= m; i++) {
		int k; read(k);
		int pos; read(pos);
		for (int j = 2; j <= k; j++) {
			int x; read(x);
			a[x].push_back(pos);
			a[pos].push_back(x);
			pos = x;
		}
	}
	tarjan(1);
	dfs(1, 0);
	ans = 0;
	for (int i = 1; i <= oldn; i++)
		chkmax(ans, dp[i][0] + dp[i][1]);
	for (int t = oldn + 1; t <= n; t++) {
		static int val[MAXN]; int tot = 0, limit = len[t] / 2;
		for (unsigned i = 0; i < b[t].size(); i++)
			if (i == b[t].size() - 1) val[++tot] = 0;
			else val[++tot] = dp[b[t][i]][0];
		for (unsigned i = 0; i < b[t].size(); i++)
			if (i == b[t].size() - 1) val[++tot] = 0;
			else val[++tot] = dp[b[t][i]][0];
		static int q[MAXN]; int l = 0, r = -1;
		for (int i = 1; i <= limit; i++) {
			while (l <= r && val[i] + i >= val[q[r]] + q[r]) r--;
			q[++r] = i;
		}
		for (int i = 1; i <= len[t]; i++) {
			if (q[l] == i) l++;
			int j = i + limit;
			while (l <= r && val[j] + j >= val[q[r]] + q[r]) r--;
			q[++r] = j;
			chkmax(ans, val[i] + val[q[l]] + q[l] - i);
		}
	}
	writeln(ans);
	return 0;
}