越多越好

题目描述:

王先生想要一些男孩帮他做一个项目。 因为这个项目是相当复杂的，需要的男孩越多越好。

当然有一定的要求，王先生要挑选一个足够大的房间来容纳这些男孩。 那些没有被选中的男孩必须马上离开房间。起初房间里有10000000个男孩，编号分别从1到10000000。 王先生要选择的男孩必须有直接或间接朋友在一起才能留下来，或只留一个男孩（0个朋友关系的时候，也要留下一个）。

现在给定若干对是朋友的编号，你来帮王先生计算一下最后最多能留下多少人。

输入格式:

输入有多组数据，每组测试数据包含：

第一行一个整数n (0 ≤ n ≤ 100 000) - 表示有n对朋友的关系。

接下来n行，每行两个数A、B，用一个空格隔开，表示A与B是直接的朋友关系 (A ≠ B, 1 ≤ A, B ≤ 10000000) 

输出格式:

只有一个数，表示剩下最多的人数。

样例输入:

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

样例输出:

4
5

时间限制: 1000ms
空间限制: 256MB

---

来源: 原创