Coloring Edges on Tree

AtCoder

IDabc146_d

Time2000ms

Memory256MB

Difficulty—

Given is a tree $G$ with $N$ vertices. The vertices are numbered $1$ through $N$, and the $i$\-th edge connects Vertex $a_i$ and Vertex $b_i$. Consider painting the edges in $G$ with some number of colors. We want to paint them so that, for each vertex, the colors of the edges incident to that vertex are all different. Among the colorings satisfying the condition above, construct one that uses the minimum number of colors. ## Constraints * $2 \le N \le 10^5$ * $1 \le a_i \lt b_i \le N$ * All values in input are integers. * The given graph is a tree. ## Input Input is given from Standard Input in the following format: $N$ $a_1$ $b_1$ $a_2$ $b_2$ $\vdots$ $a_{N-1}$ $b_{N-1}$ [samples]

Samples

Input #1

3
1 2
2 3

Output #1

2
1
2

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Coloring Edges on Tree",
    "description": {
      "content": "Given is a tree $G$ with $N$ vertices. The vertices are numbered $1$ through $N$, and the $i$\\-th edge connects Vertex $a_i$ and Vertex $b_i$. Consider painting the edges in $G$ with some number of co",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc146_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given is a tree $G$ with $N$ vertices. The vertices are numbered $1$ through $N$, and the $i$\\-th edge connects Vertex $a_i$ and Vertex $b_i$.\nConsider painting the edges in $G$ with some number of co...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments