Minimum Difference Labels in Trees

Given a tree with (N) nodes and (N-1) edges, assign integer labels to the nodes such that the maximum absolute difference between the labels of any two adjacent nodes is minimized. In other words, if the labels of two connected nodes are (a) and (b), you want to assign the labels so that (|a - b|) is as small as possible over all edges, and you wish to minimize the maximum such difference. It can be proven that if (N > 1), the minimum possible maximum difference is always 1 when assigning labels in a breadth-first order. For a tree with only one node, the answer is 0.

Input: An integer (N) on the first line, followed by (N-1) pairs of integers representing the edges of the tree.
Output: A single integer representing the minimum possible value of the maximum absolute difference between the labels of any two adjacent nodes.

inputFormat

The input is given from standard input (stdin). The first line contains an integer (N) representing the number of nodes in the tree. Each of the following (N-1) lines contains two space-separated integers representing an edge between two nodes.

outputFormat

Output to standard output (stdout) a single integer which is the minimum possible maximum absolute difference between labels of adjacent nodes. The output should be 0 if (N = 1), and 1 otherwise.## sample

1

0