在 Bajtazar 的花園裡長著一棵樹。它由 $n$ 個節點組成，編號從 $1$ 到 $n$，其中 $n$ 為偶數，且有 $n - 1$ 條樹枝，每一條直接連接兩個節點。此外，如同一般的樹，任意兩個節點之間都存在唯一一條由不重複樹枝組成的路徑。

在 Byteland，國旗日即將到來，因此 Bajtazar 決定將他樹上的節點一半塗成白色，一半塗成黑色，使其類似於 Byteland 的國旗（由於 Byteland 人重視和諧與對稱，他們的國旗由一半白色和一半黑色組成）。我們將任何這樣的著色稱為旗幟著色。

然而，如果 Bajtazar 沒有一些奇思妙想，他就不是 Bajtazar 了。他宣稱旗幟著色的美感取決於所有相同顏色節點對之間的距離總和，其中節點對之間的距離是指連接它們的路徑上的樹枝數量。

Bajtazar 希望這個總和盡可能大。請幫助他找到這個最大總和，以及任何能達到該總和的旗幟著色方式！

輸入格式

輸入的第一行包含一個偶數 $n$ ($1 \le n \le 10^6$)，代表樹中的節點數量。接下來的 $n-1$ 行包含樹枝的描述。這些行中的第 $i$ 行（對於 $1 \le i \le n-1$）包含兩個整數 $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$)，表示節點 $a_i$ 和 $b_i$ 由一條樹枝直接連接。

輸出格式

輸出的第一行應包含給定樹在旗幟著色下，相同顏色節點對之間距離的最大總和。第二行應包含一個由 $n$ 個字元組成的字串，描述達到此總和的旗幟著色。在此字串中，第 $i$ 個字元（對於 $1 \le i \le n$）若為 0 表示節點 $i$ 被塗成白色，若為 1 則表示節點 $i$ 被塗成黑色。

範例

輸入格式 1

6
1 2
2 4
2 3
1 5
5 6

輸出格式 1

14
011001

說明

範例說明：上述範例中的樹如下圖所示。節點根據上述範例輸出進行著色。白色節點之間的路徑為節點 1 與 5 之間（長度 1）、1 與 4 之間（長度 2）以及 5 與 4 之間（長度 3）。黑色節點之間的路徑為節點 2 與 3 之間（長度 1）、2 與 6 之間（長度 3）以及 3 與 6 之間（長度 4）。這些路徑長度的總和為 $1 + 2 + 3 + 1 + 3 + 4 = 14$。可以驗證，無法獲得更大的相同顏色節點之間的路徑長度總和。

範例中的樹結構

範例測試

測試 0a 為上述範例。此外：

0b：$n = 16$，且對於 $3 \le i \le n$，節點 $i$ 與節點 $i-2$ 相連。此外，節點 8 與節點 9 相連。 0c：$n = 24$，所有編號大於 1 的節點皆與節點 1 相連。 0d：$n = 5000$，編號 3 到 2501 的節點與節點 1 相連，編號 2502 到 5000 的節點與節點 2 相連。此外，節點 1 與節點 2 相連。 0e：$n = 100,000$，對於 $2 \le i \le n$，節點 $i$ 與節點 $i-1$ 相連。 0f：$n = 1,000,000$，對於 $2 \le i \le n$，節點 $i$ 與節點 $\lfloor i/2 \rfloor$ 相連。

評分

本題包含多個子任務，各子任務由一組或多組測試資料組成。

若你的輸出僅第一行正確，該測試資料可獲得 50% 的分數。你不需要輸出第二行即可獲得此部分分數。