Dans le jardin de Bajtazar pousse un arbre. Il est constitué de $n$ nœuds, numérotés de $1$ à $n$, où $n$ est pair, et possède $n - 1$ branches, chacune reliant directement deux nœuds. De plus, comme c'est généralement le cas dans les arbres, il existe exactement un chemin constitué de branches non répétées entre chaque paire de nœuds.

À Byteland, le jour du drapeau approche, et Bajtazar a décidé de colorier la moitié des nœuds de son arbre en blanc et l'autre moitié en noir, afin qu'il ressemble au drapeau de Byteland (comme les habitants de Byteland apprécient l'harmonie et la symétrie, leur drapeau est composé pour moitié de blanc et pour moitié de noir). Nous appelons un tel coloriage un coloriage de drapeau.

Bajtazar ne serait pas lui-même s'il n'avait pas ses caprices. Il a déclaré que la beauté d'un coloriage de drapeau dépend de la somme des distances entre toutes les paires de nœuds de la même couleur, où par distance entre une paire de nœuds, nous entendons le nombre de branches sur le chemin les reliant.

Bajtazar souhaite que cette somme soit la plus grande possible. Aidez-le à trouver cette somme maximale ainsi qu'un coloriage de drapeau qui l'atteint !

Entrée

La première ligne de l'entrée contient un nombre pair $n$ ($1 \le n \le 10^6$) représentant le nombre de nœuds dans l'arbre. Les $n-1$ lignes suivantes contiennent la description des branches. La $i$-ième de ces lignes (pour $1 \le i \le n-1$) contient deux entiers $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$) signifiant que les nœuds $a_i$ et $b_i$ sont directement reliés par une branche.

Sortie

La première ligne de la sortie doit contenir la somme maximale des distances entre les paires de nœuds de la même couleur dans un coloriage de drapeau de l'arbre donné. La deuxième ligne doit contenir une chaîne de $n$ caractères décrivant le coloriage de drapeau qui atteint cette somme. Dans cette chaîne, le $i$-ième caractère (pour $1 \le i \le n$) est 0 si le nœud $i$ est colorié en blanc, ou 1 s'il est colorié en noir.

Exemples

Entrée 1

6
1 2
2 4
2 3
1 5
5 6

Sortie 1

14
011001

Remarque

Explication de l'exemple : L'arbre de l'exemple ci-dessus est représenté dans la figure ci-dessous. Les nœuds sont coloriés selon la sortie de l'exemple donnée ci-dessus. Les chemins entre les nœuds blancs sont les chemins entre les nœuds 1 et 5 (longueur 1), 1 et 4 (longueur 2), et 5 et 4 (longueur 3). Les chemins entre les nœuds noirs sont les chemins entre les nœuds 2 et 3 (longueur 1), 2 et 6 (longueur 3), et 3 et 6 (longueur 4). La somme totale des longueurs de ces chemins est $1 + 2 + 3 + 1 + 3 + 4 = 14$. Il peut être vérifié qu'il n'est pas possible d'obtenir une somme plus grande des longueurs de chemins entre les nœuds de la même couleur.

Diagramme de l'arbre

Testy przykładowe

Test 0a est le test de l'exemple ci-dessus. En outre :

0b : $n = 16$ et le nœud $i$ est relié par une branche au nœud $i-2$, pour $3 \le i \le n$. De plus, le nœud 8 est relié par une branche au nœud 9.

0c : $n = 24$ et tous les nœuds numérotés plus grands que 1 sont reliés par une branche au nœud 1.

0d : $n = 5000$ et les nœuds numérotés de 3 à 2501 sont reliés par une branche au nœud 1, les nœuds numérotés de 2502 à 5000 sont reliés par une branche au nœud 2. De plus, le nœud 1 est relié par une branche au nœud 2.

0e : $n = 100\,000$ et le nœud $i$ est relié par une branche au nœud $i-1$, pour $2 \le i \le n$.

0f : $n = 1\,000\,000$ et le nœud $i$ est relié par une branche au nœud $\lfloor i/2 \rfloor$, pour $2 \le i \le n$.

Ocenianie

Si seule la première ligne de votre réponse est correcte, votre solution recevra 50 % des points pour le test donné. Vous n'avez pas besoin d'imprimer la deuxième ligne pour recevoir ces points.