#2034. 公交车与路灯修建
公交车与路灯修建
题目描述
公交车是一名道路施工员,他要为城市Z
修建路灯。
现在整个城市由个区域组成。为了方便起见,公交车把他们分别标号为 由条双向的小路连接,每块区域都可以经过一些小路到达其他的区域。公交车现在有若干种路 灯,公交车显然可以在每个区域中修建不同种类的路灯,但是为了省事,公交车想要使得使用的路灯 的种类数最小。
不幸的是,Z市市长pjh
对路灯的修建有着非常苛刻的要求。如果两块相邻(有一条小路直接连接)的
区域中修建了同一种路灯,或者即使是两块接近相邻(均可由一条小路直接连向同一块区域)的区域
也修建了同一种路灯,那么市长pjh
就会生气!
公交车必须要满足市长pjh
的要求,但是公交车却不知道如何去做,现在你要做的就是帮帮可怜的公交
车,求出整个城市Z
所需要的最少的路灯的种类数。
输入格式
输入的第一行包含。
以下行每行描述了一条小路连接的两块区域。
输出格式
输出公交车需要使用的最少的路灯的种类数
样例
输入样例
4
1 2
4 3
2 3
输出样例
3