2638 - 魔法师

给出一棵仙人掌(每条边最多被包含于一个环,无自环,无重边, 保证连通),要求用最少的颜色对其顶点染色.
满足每条边两个端点的颜色不同,输出最小颜色数即可

输入

第一行包括两个整数n,m,表示顶点数和边数
n <= 100000, m <= 200000
接下来m行每行两个整数u,v,表示u,v之间有一条无向边, 保证数据合法

输出

一行一个整数表示最小颜色数

样例

输入

3 4
1 2
2 3
3 4
1 4

输出

2

输入

5 7
2 1
2 5
3 1
3 2
4 1
4 3
5 4

输出

3
时间限制 1 秒
内存限制 512 MB
讨论 统计
上一题 下一题