小红的基环树染色构造
题号：NC311705
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

\hspace{15pt}小红拿到了一棵由 n 个点组成的基环树，她希望将每个节点都染成红，黄，蓝三种颜色中的一种，使得任意两个相邻节点的颜色都不相同。请你帮帮她。我们可以证明，答案一定存在。

【名词解释】
\hspace{15pt}基环树：对于一个包含 n 个点的简单连通图，如果其包含 n 条边，那么我们便称他为一个基环树。

输入描述:

\hspace{15pt}第一行输入一个整数 n \left(4 \leqq n \leqq 2 \times 10^5 \right)。
\hspace{15pt}之后的 n 行，每行输入两个整数 u_i, v_i \left(1 \leqq u_i, v_i \leqq n \right)，代表有一条边连接 u_i,v_i。

输出描述:

\hspace{15pt}输出 n 个整数 a_i \left(a_i \in \{1,2,3\} \right)，依次代表每个节点的颜色，其中 1 代表红色，2 代表黄色，3 代表蓝色。

\hspace{15pt}如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。
示例1

输入

复制 
4
1 2
2 3
3 1
3 4

输出

复制 
1 2 3 1

说明