3041 - 最多连通块

题目描述

给定一个由 n 个点(点的编号为 0 \sim N-1), m 条边构成的无向图。

你可以从图中任意删除 1 个点,请问最多会形成多少个连通块。

输入

本题包含多组测试数据。(不超过 120 组)

每组数据第 1 行有两个整数 N,M。(1 \le N \le 10^40 \le M \le 1.5 \times 10^4)

接下来 M 行,每行包含两个整数 x,y ,表示 x,y 两点之间有一条无向边,本题测试数据保证没有重边。(0 \le x,y \lt N)

最后读入一行 0 0 表示所有测试数据结束。

输出

对于每组测试数据,输出任意删除 1 个点之后,最多会形成的连通块的数量。

样例

输入

2 1
0 1
3 2
0 1
1 2
5 3
2 1
1 0
3 4
0 0

输出

1
2
3

输入

3 3
0 1
0 2
2 1
4 2
0 1
2 3
3 1
1 0
0 0

输出

1
2
2
标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 50
通过人数 42
金币数量 2 枚
难度 基础


上一题 下一题