Mountain Derived Subtree

Consider a rooted tree (T) with (n) nodes and root (1). A derived subtree is defined as any connected induced subgraph of (T). Its root is the node with the smallest depth in (T) among those in the subgraph. Suppose the derived subtree (T_0) has (k) levels. If we set the depth of its root to (1) and denote by (d_i) the depth of a node in (T_0), let the width (w_i) of level (i) be the number of nodes at that level. We say (T_0) is mountain‐shaped (or has a mountain structure) if its level widths form a non‐decreasing sequence, i.e., [ w_1 \le w_2 \le \cdots \le w_k. ] Your task is to find the maximum possible size (i.e. number of nodes) of a derived subtree of (T) that satisfies the above width condition.

Note the following:

• The input tree \(T\) has \(n\) nodes with node 1 as its root.
• An induced subtree is a connected set \(V_0 \subseteq V\) with all edges of \(T\) whose endpoints are in \(V_0\); its root is the node in \(V_0\) with minimum depth in \(T\). In particular, \(T\) itself is a derived subtree of \(T\).

inputFormat

The first line contains a single integer (n) ((1 \le n \le 100)). Each of the next (n-1) lines contains two integers (u) and (v) representing an edge between nodes (u) and (v). It is guaranteed that the given graph is a tree with node 1 as its root.

outputFormat

Output a single integer, the maximum size of a derived subtree of (T) whose level widths are non–decreasing.

sample

1

1