p216.ans1
======================
3
2 1 1 3 3 3 3 2
2 1 8


=================
p216.in1
======================
8 2
1 2
2 3
1 8
8 7
8 6
4 6
6 5

=================
statement.txt
======================
216. Royal Federation
time limit per test: 0.5 sec.
memory limit per test: 65536 KB
input: standard
output: standard



The king of Fooland has recently decided to reorganize his kingdom. Inspired by the democracy processes in neighbouring countries, he decided to convert his kingdom into Royal Federation. The Royal Federation would consist of several provinces, each headed by its governor.

There are N cities in his kingdom, numbered from 1 to N. Some cities are connected by roads. Roads are designed in such a way, that for each city there is exactly one way to get to any other city by the roads, not passing through any city more than once.

To prevent wastes for maintaining too small provinces, each province must contain at least B cities. However, to keep governments effective, each province must contain at most 3B cities.

Each province must have its governer headquaters in some city. This city may be outside the province itslef, but one must be able to get to the city with governer headquaters of his province in such a way, that all intermediate cities that he visits on his way belong to his province (and only the terminal city may be from another province).

One city may contain headquaters for several provinces.

Help the king to see his plans fulfilled.

Input

The first line of the input file contains two integer numbers — N and B (1 ≤ N ≤ 10 000, 1 ≤ B ≤ N). Next N-1 lines contain descriptions of roads, each line contains two integer numbers — the cities the road connects.

Output

If it is impossible to fulfil king's plans of reorganization, output 0 on the first line of the output file. In the other case output K — the number of provinces in your plan of the Royal Federation. After that output N integer numbers ranging from 1 to K — for each city output the number of the province it belongs to.

Finally output K integer numbers — the cities where the capitals of the provinces must be located in.

Sample test(s)

Input
8 2
1 2
2 3
1 8
8 7
8 6
4 6
6 5

Output
3
2 1 1 3 3 3 3 2
2 1 8
Author:	Andrew Stankevich
Resource:	Petrozavodsk Summer Trainings 2003
Date:	2003-08-30






=================
p216.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, B;
vector<vector<int>> adj;

void read() {
    cin >> n >> B;
    adj.assign(n, {});
    for(int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
}

int dfs(
    int u, int par, vector<int>& comp, vector<int>& capitals, vector<int>& st
) {
    int cnt_here = 0;
    for(int v: adj[u]) {
        if(v == par) {
            continue;
        }

        cnt_here += dfs(v, u, comp, capitals, st);
        if(cnt_here >= B) {
            capitals.push_back(u + 1);

            assert(cnt_here <= st.size());
            while(cnt_here) {
                comp[st.back()] = capitals.size();
                st.pop_back();
                cnt_here--;
            }
        }
    }

    st.push_back(u);
    cnt_here++;
    return cnt_here;
}

void solve() {
    // We can solve this "recursively" after considering an arbitrary root.
    // In particular, let dfs(u) solve the problem for the subtree rooted at u
    // if we consider the overall root is 0. Let the "highest" component covered
    // be S. We can reuse a part of S, and then join it with other components at
    // par(u). Note that the capitals don't necessary have to be a part of S, so
    // we can join multiple children of par(u), and then simply use capital(s) =
    // par(u). We have the constraint that each group should have size within
    // [B; 3 * B]. We can always cut the components (e.g. S) when it reaches
    // size >= B, and this guarantees the above. One thing we should be careful about
    // is to make sure the final component in subree(u) is connected, before joining
    // with the other children of par(u). One way to do this is by having a post-order
    // of the tree.

    vector<int> capitals, st;
    vector<int> comp(n);

    dfs(0, 0, comp, capitals, st);

    if(capitals.empty()) {
        capitals.push_back(1);
    }

    while(!st.empty()) {
        comp[st.back()] = capitals.size();
        st.pop_back();
    }

    cout << capitals.size() << endl;
    cout << comp << endl;
    cout << capitals << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
