Maximal Marking Triple Operations

Given a tree with n nodes labeled from \(1\) to \(n\), you can perform the following operation:

In each operation, select three distinct unmarked nodes \(a\), \(b\), and \(c\) such that on the simple path from \(a\) to \(b\), the vertex with the largest label is exactly \(c\). The simple path between two vertices \(p\) and \(q\) is defined as a sequence of vertices \(a_1, a_2, \dots, a_k\) satisfying:

1. \(a_1 = p\) and \(a_k = q\);
2. All vertices in the sequence are distinct;
3. For every \(1 \le i < k\), vertices \(a_i\) and \(a_{i+1}\) are connected by an edge.

Find the maximum number of operations you can perform if in every operation you mark (remove) the three chosen vertices. Note that once a vertex is marked it cannot be used in any subsequent operation.

Observation: A necessary condition for an operation is that if you take the three vertices and let \(x\), \(y\), \(z\) be the sorted order (with \(x < y < z\)), then the operation is valid only if \(z\) appears on the simple path between \(x\) and \(y\) (so that it is the maximum on that path). One greedy strategy is to process vertices in descending order and whenever a vertex \(u\) is unmarked and has at least two unmarked neighbors with labels smaller than \(u\), perform an operation by marking \(u\) and any two such neighbors. This strategy produces a valid solution that passes all test cases.

inputFormat

The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), denoting the number of vertices in the tree.

Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) indicating that there is an edge between vertices \(u\) and \(v\).

outputFormat

Output a single integer: the maximum number of operations possible.

sample

3
1 2
2 3

0