You are given a tree
T with
n vertices (numbered
1 through
n) and a letter in each vertex. The tree is rooted at vertex
1.
Let's look at the subtree
Tv of some vertex
v. It is possible to read a string along each simple path starting at
v and ending at some vertex in
Tv (possibly
v itself). Let's denote the number of
distinct strings which can be read this way as
.
Also, there's a number
cv assigned to each vertex
v. We are interested in vertices with the maximum value of
.
You should compute two statistics: the maximum value of
and the number of vertices
v with the maximum
.
Output
Print two lines.
On the first line, print
over all
1≤i≤n.
On the second line, print the number of vertices
v for which
.
Note
In the first sample, the tree looks like this:
The sets of strings that can be read from individual vertices are:
Finally, the values of
are:
In the second sample, the values of
are
(5,4,2,1,1,1). The distinct strings read in
T2 are
; note that
can be read down to vertices
3 or
4.