Rikka爱挖矿(Hard.ver)
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
最近兴起了一股淘金热，也想参加，现在为了到达挖矿地点，必须帮助解决这个问题，给定个城市，给条连接这些城市的路，从某一座城市出发，询问在不走回头路的情况下，最多能经过多少不同的城市 注： 两个版本只有数据范围不同。 数据保证， 给定一个连通图， 不存在重边， 自环，
输入格式
第一行给出一个正整数 ， 接下来 行， 给出两个城市的 ， ， 表示两个城市有一条路相连，
输出格式
输出一个数， 表示最大经过城市的数量
样例
3
1 2
2 3
3