{"problem":{"name":"Isomorphism Freak","description":{"content":"Coloring of the vertices of a tree $G$ is called a _good coloring_ when, for every pair of two vertices $u$ and $v$ painted in the same color, picking $u$ as the root and picking $v$ as the root would","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc024_d"},"statements":[{"statement_type":"Markdown","content":"Coloring of the vertices of a tree $G$ is called a _good coloring_ when, for every pair of two vertices $u$ and $v$ painted in the same color, picking $u$ as the root and picking $v$ as the root would result in isomorphic rooted trees.\nAlso, the _colorfulness_ of $G$ is defined as the minimum possible number of different colors used in a good coloring of $G$.\nYou are given a tree with $N$ vertices. The vertices are numbered $1$ through $N$, and the $i$\\-th edge connects Vertex $a_i$ and Vertex $b_i$. We will construct a new tree $T$ by repeating the following operation on this tree some number of times:\n\n*   Add a new vertex to the tree by connecting it to one of the vertices in the current tree with an edge.\n\nFind the minimum possible colorfulness of $T$. Additionally, print the minimum number of leaves (vertices with degree $1$) in a tree $T$ that achieves the minimum colorfulness.\n\n## Constraints\n\n*   $2 \\leq N \\leq 100$\n*   $1 \\leq a_i,b_i \\leq N(1\\leq i\\leq N-1)$\n*   The given graph is a tree.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$a_1$ $b_1$\n$:$\n$a_{N-1}$ $b_{N-1}$\n\n[samples]\n\n## Notes\n\nThe phrase \"picking $u$ as the root and picking $v$ as the root would result in isomorphic rooted trees\" for a tree $G$ means that there exists a bijective function $f_{uv}$ from the vertex set of $G$ to itself such that both of the following conditions are met:\n\n*   $f_{uv}(u)=v$\n*   For every pair of two vertices $(a,b)$, edge $(a,b)$ exists if and only if edge $(f_{uv}(a),f_{uv}(b))$ exists.","is_translate":false,"language":"English"}],"meta":{"iden":"agc024_d","tags":[],"sample_group":[["5\n1 2\n2 3\n3 4\n3 5","2 4\n\nIf we connect a new vertex $6$ to vertex $2$, painting the vertices $(1,4,5,6)$ red and painting the vertices $(2,3)$ blue is a good coloring. Since painting all the vertices in a single color is not a good coloring, we can see that the colorfulness of this tree is $2$. This is actually the optimal solution. There are four leaves, so we should print $2$ and $4$."],["8\n1 2\n2 3\n4 3\n5 4\n6 7\n6 8\n3 6","3 4"],["10\n1 2\n2 3\n3 4\n4 5\n5 6\n6 7\n3 8\n5 9\n3 10","4 6"],["13\n5 6\n6 4\n2 8\n4 7\n8 9\n3 2\n10 4\n11 10\n2 4\n13 10\n1 8\n12 1","4 12"]],"created_at":"2026-03-03 11:01:14"}}