<div class="post_brief"><p>
第六百道题一定要不水！虽然离第一页还有几十道题的距离。</p>

 

很早之前见过的题吧。然后一直觉得特别难写所以都没写。以前写点不重复的仙人掌都觉得挺痛苦，更不要说这个了。

 

现在想想还行，因为我yy出了化简的方法。先搞出dfs树。然后一个顶点如果是一个环里深度最浅的，那么称它为这个环的头。可以证明一个顶点最多在一个不以它为头的环上。把这个环记下来，其它的环都从这个顶点去找边来找就行了。这样的话可以比较节省代码量，写起来也比较明了。虽然还是比mhy长。

 

然后因为我在最后一步dp的时候写了一个static的f数组，所以光荣了。debug了好久。晕。

 

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;


struct edge {
int t, av;
edge *next, *rv;
};
struct ball {
int l, *a, h;
};


const int maxn = 50009;
const int maxm = 200009;
const int maxarr = 400009;


int n, m, cb, fb[maxn], d[maxn];
int f[maxn], ans, fd[maxn], fe[maxn];
int stc[maxn], tst;
int ibuf_arr[maxarr], *ibuf(ibuf_arr);
bool vis[maxn];
edge elst[maxm], *ep(elst), *head[maxn];
ball b[maxm];


inline edge* addEdge(int u, int v) {
ep-> t = v;
ep-> av = 1;
ep-> next = head[u];
return head[u] = ep ++;
}


inline void upMax(int& a, int b) {
if (a < b)
a = b;
}


void dfsBall(int p) {
vis[p] = 1;
stc[++ tst] = p;
for (edge *e = head[p]; e; e = e-> next)
if (e-> av) {
e-> rv-> av = 0;
if (vis[e-> t] && (!fb[p])) {
e-> av = 0;
b[++ cb]. l = 0;
b[cb]. a = ibuf;
for (int i = tst; 1; – i) {
b[cb]. a[b[cb]. l ++] = stc[i];
if (stc[i] != e-> t)
fb[stc[i]] = cb;
else
break;
}
b[cb]. h = e-> t;
ibuf += b[cb]. l;
}
else {
d[e-> t] = d[p] + 1;
dfsBall(e-> t);
}
}
– tst;
}


void downDP(int p) {
fd[p] = fe[p] = 0;
for (edge* e = head[p]; e; e = e-> next)
if (e-> av) {
if (fb[e-> t] && p == b[fb[e-> t]]. h) {
int bi(fb[e-> t]), fl(0);
for (int i = 0; i < b[bi]. l; ++ i)
if (b[bi]. a[i] != b[bi]. h) {
int q(b[bi]. a[i]);
downDP(q);
upMax(fl, fd[q] + min(d[q] - d[p], b[bi]. l - d[q] + d[p]));
}
if (fl > fd[p]) {
fe[p] = fd[p];
fd[p] = fl;
}
else if (fl > fe[p])
fe[p] = fl;
}
else if (!fb[p] || fb[p] != fb[e-> t]) {
downDP(e-> t);
int v(fd[e-> t] + 1);
if (v > fd[p]) {
fe[p] = fd[p];
fd[p] = v;
}
else if (v > fe[p])
fe[p] = v;
}
}
upMax(ans, fd[p] + fe[p]);
}


#define modi(i) (((i)>=b[bi].l)?((i)-b[bi].l):(i))
void upDP(int p, int u) {
static int q[maxn << 1], fu[maxn << 1];
for (edge* e = head[p]; e; e = e-> next)
if (e-> av) {
if (fb[e-> t] && p == b[fb[e-> t]]. h) {
int bi(fb[e-> t]), fl(0);
int *f(ibuf);
ibuf += b[bi]. l;
for (int i = 0; i < b[bi]. l; ++ i) {
int q(b[bi]. a[i]);
f[i] = 0;
if (q == p)
break;
fu[i] = fd[q];
upMax(fl, fd[q] + min(d[q] - d[p], b[bi]. l - d[q] + d[p]));
}
if (fl == fd[p])
fu[b[bi]. l - 1] = max(u, fe[p]);
else
fu[b[bi]. l - 1] = max(u, fd[p]);
int hd(0), tl(1), hl(b[bi]. l >> 1);
q[0] = 0;
for (int i = 1; i < (b[bi]. l << 1); ++ i) {
int fi(modi(i));
while (hd < tl && i - q[hd] > hl)
++ hd;
if (hd < tl)
upMax(f[fi], fu[modi(q[hd])] + i - q[hd]);
while (hd < tl && fu[modi(q[tl - 1])] - q[tl - 1] <= fu[fi] - i)
– tl;
q[tl ++] = i;
}
hd = 0;
tl = 1;
q[0] = (b[bi]. l << 1) - 1;
for (int i = (b[bi]. l << 1) - 2; i >= 0; – i) {
int fi(modi(i));
while (hd < tl && q[hd] - i > hl)
++ hd;
if (hd < tl)
upMax(f[fi], fu[modi(q[hd])] + q[hd] - i);
while (hd < tl && fu[modi(q[tl - 1])] + q[tl - 1] <= fu[fi] + i)
– tl;
q[tl ++] = i;
}
for (int i = 0; i < b[bi]. l - 1; ++ i) {
upMax(ans, f[i] + fd[b[bi]. a[i]]);
upDP(b[bi]. a[i], f[i]);
}
ibuf -= b[bi]. l;
}
else if (!fb[p] || fb[e-> t] != fb[p]) {
int v((fd[e-> t] + 1 == fd[p]) ? fe[p] : fd[p]);
upDP(e-> t, max(u, v) + 1);
}
}
}


int main() {
#ifndef ONLINE_JUDGE
freopen(“in.txt”, “r”, stdin);
#endif


scanf("%d%d", &amp;n, &amp;m);
memset(head, 0, sizeof(head));
for (int i = 0; i &lt; m; ++ i) {
	int c, u, v;
	scanf("%d%d", &amp;c, &amp;u);
	while (-- c) {
		scanf("%d", &amp;v);
		edge *a(addEdge(u, v)), *b(addEdge(v, u));
		a-&gt; rv = b;
		b-&gt; rv = a;
		u = v;
	}
}
memset(vis, 0, sizeof(vis));
memset(fb, 0, sizeof(fb));
cb = 0;
tst = 0;
d[1] = 1;
dfsBall(1);
ans = 0;
downDP(1);
upDP(1, 0);
printf("%d\n", ans);



}