Binary Tree Diameter Paths

Given a binary tree with \(N\) nodes and a list of \(N-1\) edges representing an undirected tree structure, your task is to compute two metrics:

• The maximum Z-path length
• The maximum O-path length

Both of these metrics are defined as the number of edges on the longest path between any two nodes in the tree (i.e. the diameter of the tree). Note that in this problem, the two metrics are identical and are equal to the tree diameter. The diamter is defined as \(\max_{u,v}\, d(u,v)\), where \(d(u,v)\) is the number of edges on the unique path between nodes \(u\) and \(v\).

If the tree contains only a single node, then both the maximum Z-path and the maximum O-path are defined to be 0.

inputFormat

The input is given via standard input:

• The first line contains an integer \(N\) (\(1 \leq N \leq 10^5\)) which is the number of nodes.
• Each of the following \(N-1\) lines contains two integers \(u\) and \(v\) indicating that there is an undirected edge between node \(u\) and node \(v\).

outputFormat

Print to standard output two integers separated by a space: the maximum Z-path length and the maximum O-path length. For a tree with one node, output "0 0".

5
1 2
1 3
2 4
2 5

3 3