{"raw_statement":[{"iden":"problem statement","content":"You are given a tree with $N$ vertices numbered $1, 2, \\dots, N$. The $i$\\-th edge connects vertices $u_i$ and $v_i$ bidirectionally.\nInitially, all vertices are painted white.\nTo efficiently visit all vertices of this tree, Alice has invented a magical gate. She uses one piece and one gate to travel according to the following procedure.\nFirst, she chooses a vertex and places both the piece and the gate on that vertex. Then, she repeatedly performs the following operations until all vertices are painted black.\n\n*   Choose one of the following actions:\n    1.  Paint the vertex where the piece is placed black.\n    2.  Choose a vertex adjacent to the vertex where the piece is placed and move the piece to that vertex. The cost of this action is $1$.\n    3.  Move the piece to the vertex where the gate is placed.\n    4.  Move the gate to the vertex where the piece is placed.\n\nNote that only the second action incurs a cost.\nIt can be proved that it is possible to paint all vertices black in a finite number of operations. Find the minimum total cost required."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq u_i, v_i \\leq N$\n*   The given graph is a tree.\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$u_1$ $v_1$\n$\\vdots$\n$u_{N-1}$ $v_{N-1}$"},{"iden":"sample input 1","content":"4\n1 2\n1 3\n1 4"},{"iden":"sample output 1","content":"3\n\nHere is an example of Alice's procedure. Let $(u, v)$ denote the state where the piece is at vertex $u$ and the gate is at vertex $v$.\n\n*   Place the piece and the gate at vertex $4$.\n    *   The state is now $(4, 4)$.\n*   Perform action $1$.\n    *   Vertex $4$ is painted black.\n    *   The state is now $(4, 4)$.\n*   Perform action $2$ and move the piece to vertex $1$.\n    *   This costs $1$.\n    *   The state is now $(1, 4)$.\n*   Perform action $1$.\n    *   Vertex $1$ is painted black.\n*   Perform action $4$.\n    *   The state is now $(1, 1)$.\n*   Perform action $2$ and move the piece to vertex $2$.\n    *   This costs $1$.\n    *   The state is now $(2, 1)$.\n*   Perform action $1$.\n    *   Vertex $2$ is painted black.\n*   Perform action $3$.\n    *   The state is now $(1, 1)$.\n*   Perform action $2$ and move the piece to vertex $3$.\n    *   This costs $1$.\n    *   The state is now $(3, 1)$.\n*   Perform action $1$.\n    *   Vertex $3$ is painted black.\n    *   All vertices are now painted black, so the procedure ends.\n\nThe total cost of performing action $2$ is $3$, and there is no procedure with a smaller cost."},{"iden":"sample input 2","content":"10\n1 7\n7 10\n10 8\n8 3\n8 4\n10 9\n9 6\n9 5\n7 2"},{"iden":"sample output 2","content":"10"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}