En el jardín de Bajtazar crece un árbol. Consiste en $n$ nodos, numerados del $1$ al $n$, donde $n$ es par, y tiene $n - 1$ ramas, cada una conectando directamente dos nodos. Además, como suele ser el caso en los árboles, existe exactamente un camino que consiste en ramas no repetidas entre cada par de nodos.

En Byteland, se acerca el Día de la Bandera, por lo que Bajtazar decidió colorear la mitad de los nodos de su árbol de blanco y la otra mitad de negro, de modo que se asemeje a la bandera de Byteland (como los habitantes de Byteland valoran la armonía y la simetría, su bandera consiste en la mitad de color blanco y la mitad de color negro). Llamamos a cualquier coloración de este tipo una coloración de bandera.

Sin embargo, Bajtazar no sería él mismo si no tuviera sus caprichos. Declaró que la belleza de una coloración de bandera depende de la suma de las distancias entre todos los pares de nodos del mismo color, donde por distancia entre un par de nodos entendemos el número de ramas en el camino que los conecta.

Bajtazar quiere que esta suma sea lo más grande posible. ¡Ayúdale a encontrar esta suma máxima y cualquier coloración de bandera que la logre!

Entrada

La primera línea de la entrada contiene un número par $n$ ($1 \le n \le 10^6$) que representa el número de nodos en el árbol. Las siguientes $n-1$ líneas contienen la descripción de las ramas. La $i$-ésima de estas líneas (para $1 \le i \le n-1$) contiene dos enteros $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$) que significan que los nodos $a_i$ y $b_i$ están conectados directamente por una rama.

Salida

La primera línea de la salida debe contener la suma máxima de las distancias entre pares de nodos del mismo color en una coloración de bandera del árbol dado. La segunda línea debe contener una cadena de $n$ caracteres que describa la coloración de bandera que logra esta suma. En esta cadena, el $i$-ésimo carácter (para $1 \le i \le n$) es 0 si el nodo $i$ está coloreado de blanco, o 1 si está coloreado de negro.

Ejemplos

Entrada 1

6
1 2
2 4
2 3
1 5
5 6

Salida 1

14
011001

Nota

Explicación del ejemplo: El árbol del ejemplo anterior se muestra en la figura de abajo. Los nodos están coloreados de acuerdo con la salida del ejemplo dada anteriormente. Los caminos entre los nodos blancos son los caminos entre los nodos 1 y 5 (longitud 1), 1 y 4 (longitud 2), y 5 y 4 (longitud 3). Los caminos entre los nodos negros son los caminos entre los nodos 2 y 3 (longitud 1), 2 y 6 (longitud 3), y 3 y 6 (longitud 4). La suma total de las longitudes de estos caminos es $1 + 2 + 3 + 1 + 3 + 4 = 14$. Se puede verificar que no es posible obtener una suma mayor de longitudes de camino entre nodos del mismo color.

Testy przykładowe

Test 0a es el test del ejemplo anterior. Además:

0b: $n = 16$ y el nodo $i$ está conectado por una rama con el nodo $i-2$, para $3 \le i \le n$. Además, el nodo 8 está conectado por una rama con el nodo 9.

0c: $n = 24$ y todos los nodos con números mayores que 1 están conectados por una rama con el nodo 1.

0d: $n = 5000$ y los nodos con números del 3 al 2501 están conectados por una rama con el nodo 1, los nodos con números del 2502 al 5000 están conectados por una rama con el nodo 2. Además, el nodo 1 está conectado por una rama con el nodo 2.

0e: $n = 100\,000$ y el nodo $i$ está conectado por una rama con el nodo $i-1$, para $2 \le i \le n$.

0f: $n = 1\,000\,000$ y el nodo $i$ está conectado por una rama con el nodo $\lfloor i/2 \rfloor$, para $2 \le i \le n$.

Ocenianie

El conjunto de pruebas se divide en los siguientes subproblemas. Las pruebas para cada subproblema consisten en uno o más grupos de pruebas separados.

Si solo la primera línea de tu respuesta es correcta, tu solución recibirá el 50% de los puntos para la prueba dada. No necesitas imprimir la segunda línea para recibir estos puntos.