Maximum Depth Sum in a Tree

You are given a rooted tree with n nodes labeled from 1 to n. The tree is rooted at node 1 and is defined by m directed edges, where each edge connects a parent to a child. The depth of a node is the number of edges on the unique path from the root to that node. Let \(d_{max}\) be the maximum depth in the tree. Your task is to calculate the sum of the node values that lie at the maximum depth, i.e., compute

\(\text{Answer} = \sum_{\text{node } v \text{ at depth } d_{max}} v\).

Note that if there is only one node (i.e.\ n = 1), then the sum is simply the value of the root node.

inputFormat

The input is read from standard input (stdin) and has the following format:

 n m
 u1 v1
 u2 v2
 ...
 um vm

Here, n is the number of nodes in the tree and m is the number of edges (for a tree, m is typically n-1; m will be 0 when n = 1). Each of the next m lines contains two integers u and v, indicating an edge from node u to node v.

outputFormat

The output is a single integer printed to standard output (stdout), which is the sum of the node values located at the maximum depth of the tree.

5 4
1 2
1 3
2 4
2 5

9