Facer's Connected Subprogram Blocks

Facer is an adorable coder who has written \(N\) programs. Interestingly, these programs are connected in such a way that for any two distinct programs \(a\) and \(b\), there exists one and only one chain connecting them. In other words, there exists a unique sequence \(a, x_1, x_2, \dots, x_n, b\) where each consecutive pair \((a, x_1), (x_1, x_2), \dots, (x_n, b)\) is directly connected. Such a collection of programs is called a program block.

Now, a subprogram block is defined as a subset \(S\) of the programs that itself forms a program block. That is, the induced graph on \(S\) is connected and, by definition, acyclic (forming a tree). Your task is to count the total number of connected subprogram blocks (i.e. connected induced subtrees) in a given program block.

Hint: If you root the tree arbitrarily, one common approach is to use dynamic programming (DP) where for each node \(u\), you compute \(dp[u] = \prod_{v \in children(u)} (dp[v] + 1)\). The final answer is \(\sum_{u=1}^{N} dp[u]\). This formula works because every connected subtree has a unique vertex that is closest to the root.

inputFormat

The first line contains a single integer \(N\) (the number of programs). The following \(N-1\) lines each contain two integers \(u\) and \(v\) representing a bidirectional connection between program \(u\) and program \(v\).

outputFormat

Output a single integer, which is the total number of connected subprogram blocks in the given program block.

sample

1

1