题目背景

题目译自 CERC 2019 「Bob in Wonderland」

题目描述

众所周知，链条是由相连的环组成的。通常，所有环都具有相同的形状和大小。Bob 是一名铁匠学徒，他正在制作自己的第一条铱链。他遵循传统的链条制作通则。上面写着：

• 如果没有链条，制作一个环，它将成为你链条的一部分。
• 如果有一条链，制作一个环，并将其连接到你已有的链中的另一个环上。

Bob 做了第一个环。然后，每次他制作另一个环时，他都会将其连接到链条上的其他环上，就像通则告诉他的那样。

当他完成时，他意识到他创造的物体根本不像一条普通的链。为了把链条拉直，他反复地拎起可能是链条两端的两个链环，并试图把它们尽可能地拉开。但在不同的地方，还有更多的“链条”从拉直的部分垂下来。

很明显，Bob 的工作还没有完成，他决定把他制作的物体称为未完成的链条。经过更多的思考，Bob 得出了一个结论，他必须更谨慎地断开一些环，并将它们重新连接到未完成的链条的其余部分，以获得他想要制作的直链。在直链中，每个环最多连接两个其他环，并且直链不能在不断开链环的情况下分离成更多的部分。

Bob 现在更加小心了，将用简单的步骤取得进展。在一个步骤中，他将选择一个环 A，连接到未完成链中的另一个环 B。然后，他会断开 A，将其与 B 分开，并将 A 重新连接到未完成的链条中的另一个环 C。如果最初连接到 A 的环不是 B，Bob 将在整个步骤中保持它们连接着 A。

Bob 获得直链所需执行的最小步骤数是多少？

输入格式

第一行包含一个整数 $N\ (1\le N\le 3\times 10^5)$，代表未完成的链条中的环数。所有环标号为 $1, 2, \dots, N$。

接下来 $N-1$ 行，每行包含两个整数，代表未完成链条中两个相连环的编号，按任意顺序给出。未完成的链条保证只有一个连体（即任意两个环之间都存在路径使他们相连）。

输出格式

输出一个整数，代表将 Bob 未完成的链条转化为直链的最少步骤数。

5
4 3
1 2
4 5
3 2

0

6
1 3
3 2
3 4
4 5
4 6

2

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

1

提示

样例解释