Bajtazarの庭には木が生えている。この木は $n$ 個のノード（$1$ から $n$ まで番号付けされている、$n$ は偶数）と、$n - 1$ 本の枝からなり、各枝は2つのノードを直接結んでいる。また、木であることの定義通り、どの2つのノードの間にも、枝を重複させないパスがちょうど1つ存在する。

Bytelandでは旗の日が近づいており、BajtazarはBytelandの旗に似せるために、木のノードの半分を白、半分を黒に塗り分けることにした（Bytelandの人々は調和と対称性を重んじるため、旗は白と黒が半分ずつで構成されている）。このような塗り分けをフラグ彩色と呼ぶ。

しかし、Bajtazarは一筋縄ではいかない。彼は、フラグ彩色の美しさは、同じ色のノードのすべてのペア間の距離の合計に依存すると述べた。ここで、ノードのペア間の距離とは、それらを結ぶパス上の枝の数を指す。

Bajtazarはこの合計を最大にしたいと考えている。彼を助け、この最大合計と、それを達成するフラグ彩色を求めよ。

入力

入力の最初の行には、木のノード数を表す偶数 $n$ ($1 \le n \le 10^6$) が含まれる。続く $n-1$ 行には枝の情報が含まれる。これらの行のうち $i$ 番目（$1 \le i \le n-1$）には、2つの整数 $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$) が含まれており、ノード $a_i$ と $b_i$ が枝で直接結ばれていることを意味する。

出力

出力の最初の行には、与えられた木のフラグ彩色における、同じ色のノードのペア間の距離の最大合計を出力せよ。2行目には、この合計を達成するフラグ彩色を表す $n$ 文字の文字列を出力せよ。この文字列の $i$ 番目の文字（$1 \le i \le n$）は、ノード $i$ が白であれば 0、黒であれば 1 とする。

入出力例

入力 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$。ノード $i$ はノード $i-2$ と枝で結ばれている ($3 \le i \le n$)。さらに、ノード 8 はノード 9 と枝で結ばれている。
• 0c: $n = 24$。ノード 1 以外のすべてのノードはノード 1 と枝で結ばれている。
• 0d: $n = 5000$。ノード 3 から 2501 はノード 1 と枝で結ばれ、ノード 2502 から 5000 はノード 2 と枝で結ばれている。さらに、ノード 1 はノード 2 と枝で結ばれている。
• 0e: $n = 100\,000$。ノード $i$ はノード $i-1$ と枝で結ばれている ($2 \le i \le n$)。
• 0f: $n = 1\,000\,000$。ノード $i$ はノード $\lfloor i/2 \rfloor$ と枝で結ばれている ($2 \le i \le n$)。

評価

テストセットは以下のサブタスクに分けられる。各サブタスクは1つ以上のテストグループで構成される。

回答の最初の行のみが正しい場合、そのテストケースの配点の50%を獲得できる。この点数を得るために2行目を出力する必要はない。