Bajtazar의 정원에는 $n$개의 노드로 이루어진 나무가 있습니다. 노드는 $1$부터 $n$까지 번호가 매겨져 있으며, $n$은 짝수입니다. 나무에는 $n - 1$개의 가지가 있고, 각 가지는 두 노드를 직접 연결합니다. 또한, 나무의 일반적인 특성과 같이 모든 두 노드 사이에는 중복되지 않는 가지들로 이루어진 경로가 정확히 하나 존재합니다.

Byteland에서는 국기 게양일이 다가오고 있습니다. Bajtazar는 나무의 노드 절반은 흰색으로, 나머지 절반은 검은색으로 칠하여 Byteland의 국기처럼 보이게 하려고 합니다(Byteland 사람들은 조화와 대칭을 중요하게 여기기 때문에, 국기는 흰색과 검은색이 절반씩 섞여 있습니다). 우리는 이러한 색칠 방식을 플래그 색칠(flag coloring)이라고 부릅니다.

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$)는 노드 $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$입니다. 같은 색 노드 사이의 경로 길이 합을 이보다 더 크게 만드는 것은 불가능함을 확인할 수 있습니다.

예제 1의 나무 구조

테스트 예제

테스트 예제 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$와 연결되어 있습니다.