Trong khu vườn của Bajtazar có một cái cây. Cây gồm $n$ nút, được đánh số từ $1$ đến $n$, trong đó $n$ là số chẵn, và có $n - 1$ nhánh, mỗi nhánh nối trực tiếp hai nút. Hơn nữa, như thường lệ đối với các cây, luôn tồn tại duy nhất một đường đi gồm các nhánh không lặp lại giữa mọi cặp nút.

Tại Byteland, ngày Quốc kỳ đang đến gần, vì vậy Bajtazar quyết định tô màu một nửa số nút của cây thành màu trắng và một nửa thành màu đen để nó giống với quốc kỳ của Byteland (vì người dân Byteland coi trọng sự hài hòa và đối xứng, quốc kỳ của họ gồm một nửa màu trắng và một nửa màu đen). Chúng ta gọi bất kỳ cách tô màu nào như vậy là một cách tô màu cờ.

Tuy nhiên, Bajtazar sẽ không phải là chính mình nếu ông không có những ý tưởng kỳ quặc. Ông tuyên bố rằng vẻ đẹp của một cách tô màu cờ phụ thuộc vào tổng khoảng cách giữa tất cả các cặp nút cùng màu, trong đó khoảng cách giữa một cặp nút là số lượng nhánh trên đường đi nối chúng.

Bajtazar muốn tổng này lớn nhất có thể. Hãy giúp ông tìm ra tổng lớn nhất đó và bất kỳ cách tô màu cờ nào đạt được nó!

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số chẵn $n$ ($1 \le n \le 10^6$) biểu thị số lượng nút trong cây. $n-1$ dòng tiếp theo chứa mô tả các nhánh. Dòng thứ $i$ trong số các dòng này (với $1 \le i \le n-1$) chứa hai số nguyên $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$) có nghĩa là các nút $a_i$ và $b_i$ được nối trực tiếp bởi một nhánh.

Dữ liệu ra

Dòng đầu tiên của dữ liệu ra nên chứa tổng khoảng cách lớn nhất giữa các cặp nút cùng màu trong một cách tô màu cờ của cây đã cho. Dòng thứ hai nên chứa một chuỗi gồm $n$ ký tự mô tả cách tô màu cờ đạt được tổng này. Trong chuỗi này, ký tự thứ $i$ (với $1 \le i \le n$) là 0 nếu nút $i$ được tô màu trắng, hoặc 1 nếu nó được tô màu đen.

Ví dụ

Dữ liệu vào 1

6
1 2
2 4
2 3
1 5
5 6

Dữ liệu ra 1

14
011001

Ghi chú

Giải thích ví dụ: Cây từ ví dụ trên được hiển thị trong hình dưới đây. Các nút được tô màu theo kết quả ví dụ đã cho ở trên. Các đường đi giữa các nút trắng là đường đi giữa nút 1 và 5 (độ dài 1), 1 và 4 (độ dài 2), và 5 và 4 (độ dài 3). Các đường đi giữa các nút đen là đường đi giữa nút 2 và 3 (độ dài 1), 2 và 6 (độ dài 3), và 3 và 6 (độ dài 4). Tổng độ dài của các đường đi này là $1 + 2 + 3 + 1 + 3 + 4 = 14$. Có thể kiểm chứng rằng không thể thu được tổng độ dài đường đi lớn hơn giữa các nút cùng màu.

Cây từ ví dụ trên

Testy przykładowe

Test 0a là test từ ví dụ trên. Ngoài ra:

0b: $n = 16$ và nút $i$ được nối với nút $i-2$, với $3 \le i \le n$. Ngoài ra nút 8 được nối với nút 9.

0c: $n = 24$ và tất cả các nút có số hiệu lớn hơn 1 đều được nối với nút 1.

0d: $n = 5000$ và các nút từ 3 đến 2501 được nối với nút 1, các nút từ 2502 đến 5000 được nối với nút 2. Ngoài ra nút 1 được nối với nút 2.

0e: $n = 100\,000$ và nút $i$ được nối với nút $i-1$, với $2 \le i \le n$.

0f: $n = 1\,000\,000$ và nút $i$ được nối với nút $\lfloor i/2 \rfloor$, với $2 \le i \le n$.

Nhiệm vụ con

Nếu chỉ dòng đầu tiên trong câu trả lời của bạn là chính xác, lời giải của bạn sẽ nhận được 50% số điểm cho bài kiểm tra đó. Bạn không cần phải in dòng thứ hai để nhận được số điểm này.