OI XXXIII - dwu

// https://szkopul.edu.pl/problemset/problem/8AZqLg3upOMpqfRyarndoGwY/site/?key=statement

#include <bits/stdc++.h>

// #define GARY_DBG
#define GARY_LIB

constexpr int sizik = 1000 * 1001;

#define ar std::array

#define int int64_t

typedef std::vector<std::vector<int>> _kra;

std::vector<int> kra[sizik];
int n;
int n_half;

int sz[sizik];
int wyn;

int flip[sizik];

void DFS(int v, int p) {
    sz[v] = 1;
    std::vector<int> dziecki;
    for (const auto& u : kra[v]) {
        if (u == p) continue;
        DFS(u, v);
        sz[v] += sz[u];
        if (sz[u] & 1) {
            dziecki.push_back(u);
        }
    }
    if (sz[v] & 1) {
        int b = (sz[v] + 1) >> 1, c = (sz[v] - 1) >> 1;
        wyn += b * (n_half - b) + c * (n_half - c);
    } else {
        int t = sz[v] >> 1;
        wyn += 2 * t * (n_half - t);
    }
    int z = (dziecki.size() + 1) / 2;
    while (dziecki.size() > z)
        dziecki.pop_back();
    for (const auto& u : dziecki) {
        flip[u] = true;
    }
}

int kol[sizik];
void DFS1(int v, int p, int c) {
    kol[v] = c;
    for (const auto& u : kra[v]) {
        if (u == p) continue;
        if (flip[u]) {
            DFS1(u, v, c ^ 1);
        } else {
            DFS1(u, v, c);
        }
    }
}

void solve() {
    std::cin >> n;
    n_half = n >> 1;

    for (int i = 0; i < n - 1; i++) {
        int a, b;
        std::cin >> a >> b;

        kra[a].push_back(b);
        kra[b].push_back(a);
    }

    DFS(1, 1);
    DFS1(1, 1, 0);

    std::cout << wyn << '\n';
    for (int i = 1; i <= n; i++) {
        std::cout << kol[i];
    }
    std::cout << '\n';
}

int32_t main() {
#ifndef GARY_DBG
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
#endif

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}