I. Color the Tree
time limit per test
7 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a tree consisting of $$$n$$$ vertices. Initially, none of the vertices of the tree are colored.

You can perform the following operation: choose any two vertices $$$u$$$ and $$$v$$$ (you are allowed to choose $$$u=v$$$) and color all the vertices on the path between them (including the endpoints) with color $$$i$$$, where $$$i$$$ is the index of the operation you are performing (that is, the first operation uses color $$$1$$$, the second uses color $$$2$$$, and so on). If any vertex on the path has already been colored before, its color changes to the new one.

We call the coloring of the tree complete if for each vertex, at least one operation has colored it.

Your task is to calculate two values:

  • the minimum number of operations required to achieve a complete coloring;
  • the number of distinct complete colorings that can be obtained with the minimum number of operations (two colorings are considered different if there exists at least one vertex $$$v$$$ such that the color of $$$v$$$ in the first coloring differs from the color of $$$v$$$ in the second coloring).
Input

The first line contains a single integer $$$n$$$ ($$$3 \le n \le 32$$$) — the number of vertices in the tree.

The next $$$(n-1)$$$ lines contain two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$) — the endpoints of the next edge of the tree.

Additional constraint on the input: the edges define a valid tree with $$$n$$$ vertices.

Output

Print two integers — the minimum number of operations and the number of distinct complete colorings that can be obtained with the minimum number of operations. Since the second number can be very large, output it modulo $$$998244353$$$.

Examples
Input
3
1 2
2 3
Output
1 1
Input
5
1 3
2 1
5 1
1 4
Output
2 6
Input
4
1 4
2 4
4 3
Output
2 9
Input
5
4 2
1 5
3 4
4 1
Output
2 11
Input
10
7 9
9 3
4 2
8 7
7 10
8 5
4 1
8 2
6 8
Output
3 270