Isomorphism Freak

AtCoder

IDagc024_d

Time2000ms

Memory256MB

Difficulty—

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. Also, the _colorfulness_ of $G$ is defined as the minimum possible number of different colors used in a good coloring of $G$. You 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: * Add a new vertex to the tree by connecting it to one of the vertices in the current tree with an edge. Find 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. ## Constraints * $2 \leq N \leq 100$ * $1 \leq a_i,b_i \leq N(1\leq i\leq N-1)$ * The given graph is a tree. ## Input Input is given from Standard Input in the following format: $N$ $a_1$ $b_1$ $:$ $a_{N-1}$ $b_{N-1}$ [samples] ## Notes The 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: * $f_{uv}(u)=v$ * For every pair of two vertices $(a,b)$, edge $(a,b)$ exists if and only if edge $(f_{uv}(a),f_{uv}(b))$ exists.

Samples

Input #1

Output #1

2 4

If 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$.

Input #2

Output #2

3 4

Input #3

Output #3

4 6

Input #4

Output #4

4 12

API Response (JSON)

{
  "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...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments