Contents
Mashtali vs AtCoder solution codeforces

For Solution
Click Here!
After many unsuccessful tries, Mashtali decided to copy modify an AtCoder problem. So here is his copied new problem:
There is a tree with nn vertices and some nonempty 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). Mashtali vs AtCoder solution codeforces
You are given the tree, but not the set of the pinned vertices. Your task is to determine, for each kk, the winner of the game, if only the vertices 1,2,3,…,k1,2,3,…,k are pinned and both players play optimally.
The first line of input contains an integer nn — the number of vertices (1≤n≤3⋅1051≤n≤3⋅105).
The iith of the following n−1n−1 lines contains two integers ui,viui,vi (1≤ui,vi≤n1≤ui,vi≤n, ui≠viui≠vi) — the endpoints of the iith edge. It’s guaranteed that these edges form a tree.
Print a string of length nn. The iith character should be ‘1’ if the first player wins the iith scenario, and ‘2’ otherwise.
input Mashtali vs AtCoder solution codeforces
5 1 2 2 3 2 4 4 5
output
11122
input Mashtali vs AtCoder solution codeforces
5 1 2 2 3 1 4 4 5
output
21122
input Mashtali vs AtCoder solution codeforces
6 1 2 2 4 5 1 6 3 3 2
output
111111
input Mashtali vs AtCoder solution codeforces
7 1 2 3 7 4 6 2 3 2 4 1 5
output Mashtali vs AtCoder solution codeforces
2212222
Below you can see the tree in the first sample :
If k=2k=2 or k=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.

For Solution
Click Here!