Problem Statement

You are given a tree consisting of N nodes numbered from 1 to N. (Recall that a tree is a connected, undirected graph with exactly N − 1 edges and no cycles.) You are allowed to add new undirected edges between any pair of nodes that are not already directly connected. However, there is a strict rule: the resulting graph must not contain any cycle of odd length (for example, you cannot form a cycle of 3, 5, or 7 nodes). Calculate the maximum number of new edges you can add to the tree such that this rule is never violated. Input Format The first line contains a single integer N — the number of nodes. Each of the next N − 1 lines contains two integers u and v denoting an undirected edge between nodes u and v. Output Format Print a single integer — the maximum number of new edges that can be added without ever creating an odd-length cycle. Constraints 1 ≤ N ≤ 2 × 10 5 1 ≤ u, v ≤ N The given edges are guaranteed to form a valid tree. Sample Input