C. За какую вершину подвесить

Та же игра, что в задаче A: рубим ребро, отваливается всё, что отделилось от корня. Но теперь корень не задан: нужно для каждой вершины сказать, кто выиграет, если подвесить дерево именно за неё.

В первой строке $n$ ($2 \le n \le 2 \cdot 10^5$). В следующих $n-1$ строках по два числа — концы ребра.

Выведите строку из $n$ символов: $i$-й равен 1, если при подвешивании за вершину $i$ выигрывает первый игрок, и 2 иначе.