Mashtali vs AtCoder solution codeforces

Mashtali vs AtCoder solution codeforces

After many unsuccessful tries, Mashtali decided to copy modify an AtCoder problem. So here is his copied new problem:

There is a tree with 𝑛n vertices and some non-empty set of the vertices are pinned to the ground.

Two players play a game against each other on the tree. They alternately perform the following action:

  • Remove an edge from the tree, then remove every connected component that has no pinned vertex.The player who cannot move loses(every edge has been deleted already).

You are given the tree, but not the set of the pinned vertices. Your task is to determine, for each 𝑘k, the winner of the game, if only the vertices 1,2,3,,𝑘1,2,3,…,k are pinned and both players play optimally.

Input

The first line of input contains an integer 𝑛n — the number of vertices (1𝑛31051≤n≤3⋅105).

The 𝑖i-th of the following 𝑛1n−1 lines contains two integers 𝑢𝑖,𝑣𝑖ui,vi (1𝑢𝑖,𝑣𝑖𝑛1≤ui,vi≤n𝑢𝑖𝑣𝑖ui≠vi) — the endpoints of the 𝑖i-th edge. It’s guaranteed that these edges form a tree.

Output

Print a string of length 𝑛n. The 𝑖i-th character should be ‘1’ if the first player wins the 𝑖i-th scenario, and ‘2’ otherwise.

Examples
input

Copy Mashtali vs AtCoder solution codeforces

5
1 2
2 3
2 4
4 5
output

Copy
11122
input

Copy
5
1 2
2 3
1 4
4 5

output Mashtali vs AtCoder solution codeforces

21122
input

Copy
6
1 2
2 4
5 1
6 3
3 2
output

Copy
111111
input

Copy
7
1 2
3 7
4 6
2 3
2 4
1 5
output

Copy
2212222

Note Mashtali vs AtCoder solution codeforces

Below you can see the tree in the first sample :

If 𝑘=1k=1 then the first player can cut the edge (1,2)(1,2).

If 𝑘=2k=2 or 𝑘=3k=3, the first player can cut the edge (2,4)(2,4), after that only the edges (1,2)(1,2) and (2,3)(2,3) remain. After the second players move, there will be a single edge left for the first player to cut. So first player wins.

Leave a Comment

Your email address will not be published. Required fields are marked *