Ở trong thành phố Bedao, nơi mọi người rất yêu thích những cái cây. Hôm nay thị trưởng Copium đã cho tổ chức một cuộc thi tô màu, đề bài là cho một cây với ~n~ node và ~n - 1~ cạnh, cạnh thứ ~i~ nối giữa ~2~ node ~u_i~ và ~v_i~ có chiều dài là ~w_i~. Hãy tô mỗi node màu đỏ hoặc đen sao cho độ dài giữa ~2~ node cùng màu bất kỳ luôn là chẵn. Phần thưởng dành cho người nhanh nhất sẽ là một khoản tiền rất lớn, nên bạn hãy cố gắng chiến thắng cuộc thi đó nhé!

Input

• Dòng đầu tiên chứa số nguyên ~n~, là số node của cây ~(1 \le n \le 10^5)~
• Trong ~n - 1~ dòng kế tiếp, mỗi dòng chứa ~3~ số nguyên ~u_i~, ~v_i~ và ~w_i~, biểu diễn cạnh nối giữa ~u_i~, ~v_i~ và có độ dài là ~w_i~ ~(1 \le u_i, v_i \le n, 1 \le w_i \le 10^9)~

Output

• Gồm ~n~ số nguyên. Số thứ ~i~ là ~0~ nếu node ~i~ được tô màu đỏ, còn ~1~ nếu node ~i~ được tô màu đen. Nếu có nhiều phương án, hãy in ra phương án bất kỳ.

Sample Input 1

3
2 3 1
2 1 2

Sample Output 1

1 1 0

Sample Input 2

5
2 5 2
2 3 10
1 3 8
3 4 2

Sample Output 2

1 0 1 0 1

Subtask

• ~20\%~ số test có ~n \le 10~.
• ~80\%~ số test còn lại không có điều kiện gì thêm.

Note

Trong ví dụ thứ ~2~ sẽ có nhiều đáp án khác nhau, chẳng hạn như ~[1, 1, 1, 1, 1]~ vẫn được xem là hợp lệ.