#325. 刀斯林计划

传统 1500 ms 256 MiB
标准 IO
文本比较 Demerzel 标签

题目描述

你们这群叛徒,给我老实呆着,看我派坦克来,把你们一个个都送上天!
————第一届汉城战车道竞速赛举办者 张泰玩

阿树是电子竞技协会 DOTA2 分部的部长。

游戏的人气不景气,新部员逐年减少,部内死气沉沉,阿树看在眼里,急在心里。

可是最近,阿树发现了另一件更糟糕的事情。

这两天,当阿树经过有些部员的时候,听到他们在说一些奇怪的话,诸如“重铸 XX 荣光,吾辈义不容辞”之类。

借由各种渠道,阿树才了解到,原来这是来自 LOL 的“名言”!

感觉受到了背叛的阿树怒火中烧,未曾想在外患之外,萧墙之内居然先出了内鬼。他决心要把叛徒们都揪出来,维护队伍的纯洁,誓与 LOL 势不两立。

为了表明自己的决心,他将这次行动命名为“刀斯林计划”。

现在,经由详细而隐蔽的调查,阿树已经确定了 nn 个叛徒。他准备举办一场盛大的公开审判,以同好聚会为借口,要求部里所有的人到场。在现场,他会突然揭开这些叛徒的真面目,并且用减免惩罚来利诱叛徒们互相揭发指控。这样,阿树一方面可以惩戒这些叛徒,另一方面也可以通过这场公审对人群里其他潜藏的内鬼起到敲山震虎的作用,可谓一举两得。

但是,在调查中阿树也发现,叛徒之间也往往存在着交情。在这 nn 个叛徒之间,共存在着恰好 nn 个朋友关系,每个关系联系着两个不同的叛徒。如果把叛徒视为点,朋友关系视为边,则可以构成一个 nn 个点,nn 条边的无向连通图。图中不存在重边和自环。

如果阿树把具有朋友关系的两个人同时加入审判名单,那么,他们在公审中就会互相包庇,审判也会失去震慑力,变成闹剧,这显然是阿树无法忍受的。因此,对于最终的名单,其中任意两个人都不能具有朋友关系。

现在,阿树想要知道,如果他以最优的方法选取叛徒进行审判,名单上最多可以有多少人?

输入格式

输入包含多组数据。

每组数据的第一行是一个整数 n(3n106)n(3 \leq n \leq 10^6),代表了叛徒人数和朋友关系的数目。接下来 nn 行,每行两个不同的整数 u,v(1u,vn)u,v(1 \leq u,v \leq n),代表一个关系联系的两个叛徒。

数据保证叛徒之间构成一个连通图,且不存在重边和自环。

一组测试数据中的 nn 之和不大于 10610^6

输出格式

对每一组数据,输出一个正整数,代表阿树的名单上最多可以罗列的叛徒的数目。

样例

样例输入1

5
1 3
5 2
4 2
4 3
2 1

样例输出1

3

样例输入2

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

样例输出2

2
3