3651. 消防演练

【题目描述】

某市的道路网络由$n$个路口和$n-1$条双向道路组成，每条道路连接两个不同的路口，使得任意两个路口都可以经过若干条道路相互到达。

恰逢消防日，消防大队决定进行一次消防车演练：方式是从某一个路口出发，经过若干条道路到达另外一个路口。当然，为了保证效率，消防车不会经过任意一条道路两次。

为了保证消防车顺利通行和群众安全，所有恰有一端在消防车路线上(包括起点和终点)的道路都会被封锁。

你的任务是求出被封锁的道路数量的最大值。

【输入格式】

输入第一行包含一个正整数$n$，表示城市的路口数。

接下来$n-1$行，每行两个正整数$x,y$，表示有一条双向道路连接路口$x$和路口$y$。

【输出格式】

输出一个整数，表示被封锁的道路数量的最大值。

【样例输入】

8
1 2
2 3
4 2
5 2
6 5
5 7
7 8

【样例输出】

5

【样例说明】

游行路线：2-5-7。被封锁的道路：(1,2),(2,3),(4,2),(6,5),(7,8)。

大样例

【数据规模和约定】

对于30%的数据，$n\leq 100$；

对于50%的数据，$n\leq 1000$；

对于100%的数据，$2\leq n\leq 2\times 10^5,1\leq x, y\leq n, x\neq y$。