#include <bits/stdc++.h>

using namespace std;
template<class T>
using Matrix = vector<vector<T>>;


// Lin-Kernighan

struct Tour {
public:
    virtual int size() = 0;

    virtual int next(int v) = 0;

    virtual int prev(int v) = 0;

    // flip indices between a and b, both inclusive.
    virtual void flip(int a, int b) = 0;

    // if b lies in the segment of the tour from a to c;
    virtual bool sequence(int a, int b, int c) = 0;

    virtual vector<int> get_tour_from(int v = 0) = 0;
};


struct ArrayTour : Tour {
private:
    vector<int> tour;
    vector<int> inverse;
    bool reversed;
    int n;

public:
    ArrayTour(int an) {
        assert(an > 0);
        reversed = false;
        n = an;
        tour.resize(n);
        iota(tour.begin(), tour.end(), 0);
        inverse.resize(n);
        iota(inverse.begin(), inverse.end(), 0);
    }

    ArrayTour(vector<int> initial_tour) {
        assert(initial_tour.size() > 0);
        reversed = false;
        n = initial_tour.size();
        tour = initial_tour;
        inverse.resize(n);
        for (int i = 0; i < n; i++) {
            inverse[tour[i]] = i;
        }
    }

    int size() {
        return n;
    }

    int next(int v) {
        int i_v = inverse[v];
        int i_next = i_v + (reversed ? -1 : 1);
        if (i_next < 0) i_next += n;
        if (n <= i_next) i_next -= n;
        return tour[i_next];
    }

    int prev(int v) {
        int i_v = inverse[v];
        int i_prev = i_v + (reversed ? 1 : -1);
        if (i_prev < 0) i_prev += n;
        if (n <= i_prev) i_prev -= n;
        return tour[i_prev];
    }

    void flip(int a, int b) {
        if (a == b) return;

        int flip_len = abs(inverse[a] - inverse[b]) + 1;
        assert(2 <= flip_len && flip_len <= n);
        if ((inverse[a] > inverse[b]) ^ reversed) {
            flip_len = n - flip_len + 2;
        }
        assert(2 <= flip_len && flip_len <= n);

        if (flip_len == n) {
            reversed ^= 1;
            return;
        }
        if (flip_len > n - flip_len) {
            assert(n - flip_len >= 1);
            flip(next(b), prev(a));
            reversed ^= 1;
            return;
        }

        while (a != b) {
            int a_next = next(a);
            int b_prev = prev(b);
            swap(tour[inverse[a]], tour[inverse[b]]);
            swap(inverse[a], inverse[b]);
            if (a_next == b) {
                assert(b_prev == a);
                break;
            }
            a = a_next;
            b = b_prev;
        }
    }

    vector<int> get_tour_from(int v = 0) {
        vector<int> ret(n);
        ret[0] = v;
        for (int i = 0; i < n; i++, v = next(v)) {
            ret[i] = v;
        }
        return ret;
    }

    bool sequence(int a, int b, int c) {
        if (a == b || c == b) return true;
        if (a == c) return (a == b);
        if (inverse[a] < inverse[c]) {
            if (!reversed) {
                return (inverse[a] < inverse[b] && inverse[b] < inverse[c]);
            } else {
                return (inverse[b] < inverse[a] || inverse[c] < inverse[b]);
            }
        } else {
            if (!reversed) {
                return (inverse[a] < inverse[b] || inverse[b] < inverse[c]);
            } else {
                return (inverse[b] < inverse[a] && inverse[c] < inverse[b]);
            }
        }
    }
};

template<class T, size_t compare_pos = 0>
struct Ordering {
public:
    int size;
    vector<T> sorted;

    Ordering(int size_, T default_value) {
        size = size_;
        sorted.assign(size, default_value);
    }

    void insert(T value) {
        int k = 0;
        for (; k + 1 < size && get<compare_pos>(sorted[k + 1]) < get<compare_pos>(value); k++) {
            sorted[k] = sorted[k + 1];
        }
        sorted[k] = value;
    }
};

// TODO: use abstract Tour class
template<class Cost>
struct LinKernighan {
private:
    int n;
    ArrayTour tour;
    Matrix<Cost> G;
    Matrix<int> neighbors;

    // TODO: use hash?
    vector<vector<bool>> is_added;
    vector<vector<bool>> is_deleted;

    vector<bool> marked;
    queue<int> que;

    vector<tuple<int, int>> flip_stack;
    Cost total_delta;

    mt19937 mt;

    const int max_level = 25;
    const vector<int> breadths = {4, 3, 3, 2};
    const int breadth_A = 4;
    const int breadth_B = 3;
    const int breadth_D = 3;

    void mark_edge_added(int a, int b) {
        is_added[a][b] = true;
        is_added[b][a] = true;
    }

    void unmark_edge_added(int a, int b) {
        is_added[a][b] = false;
        is_added[b][a] = false;
    }

    void mark_edge_deleted(int a, int b) {
        is_deleted[a][b] = true;
        is_deleted[b][a] = true;
    }

    void unmark_edge_deleted(int a, int b) {
        is_deleted[a][b] = true;
        is_deleted[b][a] = true;
    }

    void flip(int a, int b) {
        tour.flip(a, b);
        flip_stack.emplace_back(a, b);
    }

    void undo_last_flip() {
        int a, b;
        tie(a, b) = flip_stack.back();
        flip_stack.pop_back();
        tour.flip(b, a);
    }

    void chained_lin_kernighan(int stall_count, int repeat_count) {
        total_delta = 0;
        flip_stack.clear();
        lin_kernighan();

        int quit_count = min(stall_count, repeat_count);
        for (int round = 0; round < quit_count; round++) {
            total_delta = 0;
            flip_stack.clear();

            kick();
            lin_kernighan();

            if (total_delta <= 0) {
                while (!flip_stack.empty()) {
                    undo_last_flip();
                }
            } else {
                quit_count = min(round + stall_count, repeat_count);
            }
        }
    }

#define LONG_KICKER

    int first_kicker() {
        int t1;
#ifdef LONG_KICKER
        int longcount = int(n * 0.001) + 10;

        int base = mt() % n;
        int next_of_base = tour.next(base);
        int prev_of_base = tour.next(base);
        t1 = G[base][next_of_base] == G[prev_of_base][base] ? prev_of_base : base;
        int best_score = G[t1][tour.next(t1)] - G[t1][neighbors[t1][0]];

        for (int i = 0; i < longcount; i++) {
            base = mt() % n;
            next_of_base = tour.next(base);
            prev_of_base = tour.next(base);
            int new_t1 = G[base][next_of_base] == G[prev_of_base][base] ? prev_of_base : base;
            int score = G[new_t1][tour.next(t1)] - G[new_t1][neighbors[new_t1][0]];

            if (score > best_score) {
                best_score = score;
                t1 = new_t1;
            }
        }
#else
        t1 = mt() % n;
#endif
        return t1;
    }

    void kick() {
        int t1, t2, t3, t4, t5, t6, t7, t8;
        // TODO: geometric kicker

        {
            // random kicker
            t1 = first_kicker();
            t2 = tour.next(t1);

            do {
                t3 = mt() % n;
                t4 = tour.next(t3);
            } while (t3 == t1 || t3 == t2 || t4 == t1);

            do {
                t5 = mt() % n;
                t6 = tour.next(t5);
            } while (t5 == t1 || t5 == t2 || t5 == t3 || t5 == t4 || t6 == t1 || t6 == t3);

            do {
                t7 = mt() % n;
                t8 = tour.next(t7);
            } while (t7 == t1 || t7 == t2 || t7 == t3 || t7 == t4 || t7 == t5 || t7 == t6 ||
                     t8 == t1 || t8 == t3 || t8 == t5);
        }

        // sort order
        if (!tour.sequence(t1, t3, t5)) {
            swap(t3, t5);
            swap(t4, t6);
            // we can assert t1 -> t2 ---> t3 -> t4 ---> t5 -> t6
        }
        if (!tour.sequence(t1, t5, t7)) {
            swap(t5, t7);
            swap(t6, t8);
            // we can assert t1 -> t2 ---> t5 -> t6 ---> t7 -> t8
            if (!tour.sequence(t1, t3, t5)) {
                swap(t3, t5);
                swap(t4, t6);
                // we can assert t1 -> t2 ---> t3 -> t4 ---> t5 -> t6 ---> t7 -> t8
            }
        }

        flip(t2, t5);
        flip(t3, t7);
        flip(t5, t6);
        total_delta += G[t1][t2] - G[t1][t6] + G[t3][t4] - G[t3][t8] + G[t5][t6] - G[t5][t2] + G[t7][t8] - G[t7][t4];
    }

    void mark(int v) {
        if (marked[v]) return;
        marked[v] = true;
        que.push(v);
    }

    Cost total_cost() {
        vector<int> vec_tour = tour.get_tour_from(0);
        Cost cost = G[vec_tour[n - 1]][vec_tour[0]];
        for (int i = 0; i + 1 < n; i++) {
            int a = vec_tour[i];
            int b = vec_tour[i + 1];
            cost += G[a][b];
        }
        return cost;
    }

    void lin_kernighan() {
        marked.assign(n, true);
        for (int i = 0; i < n; i++) {
            que.push(i);
        }

        while (!que.empty()) {
            int base = que.front();
            int next_of_base = tour.next(base);

            mark_edge_deleted(base, next_of_base);
            bool found = (step(base, 0, 0) || alternate_step(base));
            unmark_edge_deleted(base, next_of_base);

            marked[base] = false;
            que.pop();

            if (found) {
                mark(base);
                mark(next_of_base);
            }
        }
    }

    bool step(int base, int level, Cost delta) {
        // lk-ordering
        int breadth = level < breadths.size() ? breadths[level] : 1;
        int next_of_base = tour.next(base);
        for (int i = 0; i < breadth; i++) {
            // (priority, is_mm, a) in ascending order
            Ordering<tuple<Cost, bool, int>> lk_ordering(breadth, make_tuple(numeric_limits<Cost>::min(), false, -1));

            {
                int next_of_next_of_base = tour.next(next_of_base);
                for (int a : neighbors[next_of_base]) {
                    if (delta + G[base][next_of_base] - G[next_of_base][a] <= 0) break;
                    if (is_deleted[next_of_base][a] || a == base || a == next_of_next_of_base) continue;
                    int prev_of_a = tour.prev(a);
                    if (is_added[a][prev_of_a]) continue;
                    Cost priority = G[prev_of_a][a] - G[next_of_base][a];
                    lk_ordering.insert(make_tuple(priority, false, a));
                }
            }

            // Mak-Morton move
            {
                int prev_of_base = tour.prev(base);
                for (int a : neighbors[base]) {
                    if (delta + G[base][next_of_base] - G[base][a] <= 0) break;
                    if (is_deleted[base][a] || a == next_of_base || a == prev_of_base) continue;
                    int next_of_a = tour.next(a);
                    if (is_added[a][next_of_a]) continue;
                    Cost priority = G[a][next_of_a] - G[base][a];
                    lk_ordering.insert(make_tuple(priority, true, a));
                }
            }

            for (auto &t : lk_ordering.sorted) {
                bool is_mm = get<1>(t);
                int a = get<2>(t);

                if (a == -1) continue;

                if (is_mm) {
                    int next_of_a = tour.next(a);
                    Cost gain = G[base][next_of_base] - G[base][a] + G[a][next_of_a] - G[next_of_a][next_of_base];

                    mark_edge_added(base, a);
                    mark_edge_deleted(a, next_of_a);

                    flip(next_of_a, base);
                    bool found = step(next_of_a, level + 1, delta + gain);

                    unmark_edge_added(base, a);
                    unmark_edge_deleted(a, next_of_a);

                    if (found || (gain > 0 && delta + gain > 0)) {
                        if (!found) {
                            total_delta += delta + gain;
                        }
                        mark(base);
                        mark(next_of_a);
                        return true;
                    } else {
                        // unflip
                        undo_last_flip();
                    }
                } else {
                    int prev_of_a = tour.prev(a);
                    Cost gain = G[base][next_of_base] - G[next_of_base][a] + G[prev_of_a][a] - G[prev_of_a][base];

                    mark_edge_added(next_of_base, a);
                    mark_edge_deleted(a, prev_of_a);

                    flip(next_of_base, prev_of_a);
                    bool found = step(base, level + 1, delta + gain);

                    unmark_edge_added(next_of_base, a);
                    unmark_edge_deleted(a, prev_of_a);

                    if (found || (gain > 0 && delta + gain > 0)) {
                        if (!found) {
                            total_delta += delta + gain;
                        }
                        mark(next_of_base);
                        mark(prev_of_a);
                        return true;
                    } else {
                        // unflip
                        undo_last_flip();
                    }
                }
            }
        }
        return false;
    }

    bool alternate_step(int base) {
        int s1 = tour.next(base);

        // (priority, a) in ascending order
        Ordering<tuple<Cost, int>> A_ordering(breadth_A, make_tuple(numeric_limits<Cost>::min(), -1));

        for (int a : neighbors[s1]) {
            if (G[base][s1] - G[s1][a] <= 0) break;
            if (a == base) continue;
            int next_of_a = tour.next(a);
            if (next_of_a == base) continue;
            Cost priority = G[next_of_a][a] - G[s1][a];
            A_ordering.insert(make_tuple(priority, a));
        }

        for (auto &t_a : A_ordering.sorted) {
            int a = get<1>(t_a);
            if (a == -1) continue;

            int a1 = tour.next(a);

            mark_edge_added(s1, a);
            mark_edge_deleted(a, a1);

            // (priority, seq, side, b) in ascending order
            Ordering<tuple<Cost, bool, bool, int>> B_ordering(breadth_B,
                                                              make_tuple(numeric_limits<Cost>::min(), false, false,
                                                                         -1));

            for (int b : neighbors[a1]) {
                if (G[base][s1] - G[s1][a] + G[a][a1] - G[a1][b] <= 0) break;
                if (b == a || b == a1 || b == base || b == s1) continue;
                bool seq = tour.sequence(s1, b, a);
                if (seq) {
                    int b1 = tour.next(b);
                    if (!(b1 == a || b1 == a1 || b1 == base || b1 == s1)) {
                        B_ordering.insert(make_tuple(G[b1][b] - G[a1][b], true, true, b));
                    }
                }
                int b1 = tour.prev(b);
                if (b1 == a || b1 == base || b1 == s1 || b1 == a1) continue;
                B_ordering.insert(make_tuple(G[b1][b] - G[a1][b], seq, false, b));
            }

            for (auto &t_b : B_ordering.sorted) {
                int b = get<3>(t_b);
                if (b == -1) continue;

                bool seq_b = get<1>(t_b);
                bool side_b = get<2>(t_b);
                int b1 = side_b ? tour.next(b) : tour.prev(b);

                mark_edge_added(a1, b);
                mark_edge_deleted(b, b1);

                if (seq_b) {
                    Cost delta = G[base][s1] - G[base][b1] + G[a][a1] - G[a][s1] + G[b][b1] - G[b][a1];
                    if (side_b) {
                        flip(s1, a);
                        flip(b, s1);
                        flip(a, b1);
                    } else {
                        flip(s1, b1);
                        flip(b, a);
                    }

                    bool found = step(base, 2, delta);

                    if (found || delta > 0) {
                        if (!found) {
                            total_delta += delta;
                        }

                        unmark_edge_added(s1, a);
                        unmark_edge_deleted(a, a1);
                        unmark_edge_added(a1, b);
                        unmark_edge_deleted(b, b1);

                        // mark
                        if (side_b) {
                            mark(s1);
                            mark(a);
                            mark(b);
                            mark(b1);
                        } else {
                            mark(s1);
                            mark(a);
                            mark(b);
                            mark(b1);
                        }
                        return true;
                    } else {
                        // unflip
                        if (side_b) {
                            undo_last_flip();
                            undo_last_flip();
                            undo_last_flip();
                        } else {
                            undo_last_flip();
                            undo_last_flip();
                        }
                    }
                } else {
                    assert(!side_b);  // assert b1 is the previous node of b

                    // (priority, side, b) in ascending order
                    Ordering<tuple<Cost, bool, int>> D_ordering(breadth_D,
                                                                make_tuple(numeric_limits<Cost>::min(), false, -1));

                    for (int d : neighbors[b1]) {
                        if (G[base][s1] - G[s1][a] + G[a][a1] - G[a1][b] + G[b][b1] - G[b1][d] <= 0) break;
                        if (d == b || d == b1 || d == a || d == a1 || d == base || d == s1) continue;
                        if (!tour.sequence(s1, d, a)) continue;
                        {
                            int d1 = tour.next(d);
                            if (!(d1 == b || d1 == b1 || d1 == a || d1 == a1 || d1 == base || d1 == s1)) {
                                D_ordering.insert(make_tuple(G[d1][d] - G[b1][d], true, d));
                            }
                        }
                        {
                            int d1 = tour.prev(d);
                            if (!(d1 == b || d1 == b1 || d1 == a || d1 == a1 || d1 == base || d1 == s1)) {
                                D_ordering.insert(make_tuple(G[d1][d] - G[b1][d], false, d));
                            }
                        }
                    }

                    for (auto &t_d : D_ordering.sorted) {
                        int d = get<2>(t_d);
                        if (d == -1) continue;

                        bool side_d = get<1>(t_d);
                        int d1 = side_d ? tour.next(d) : tour.prev(d);
                        Cost delta = G[base][s1] - G[base][d1]
                                     + G[a][a1] - G[a][s1]
                                     + G[b][b1] - G[b][a1]
                                     + G[d][d1] - G[d][b1];

                        Cost cost_before = total_cost();
                        if (side_d) {
                            flip(s1, b1);
                            flip(b1, d1);
                            flip(a1, s1);
                        } else {
                            flip(s1, d1);
                            flip(d, a);
                            flip(a1, b1);
                        }
                        Cost cost_after = total_cost();
                        assert(cost_before - delta == cost_after);

                        mark_edge_added(b1, d);
                        mark_edge_deleted(d, d1);
                        bool found = step(base, 2, delta);
                        unmark_edge_added(b1, d);
                        unmark_edge_deleted(d, d1);

                        if (found || delta > 0) {
                            if (!found) {
                                total_delta += delta;
                            }

                            unmark_edge_added(s1, a);
                            unmark_edge_deleted(a, a1);
                            unmark_edge_added(a1, b);
                            unmark_edge_deleted(b, b1);

                            // mark
                            if (side_d) {
                                mark(s1);
                                mark(b1);
                                mark(d1);
                                mark(a1);
                            } else {
                                mark(s1);
                                mark(d1);
                                mark(d);
                                mark(a);
                                mark(a1);
                                mark(b1);
                            }
                            return true;
                        } else {
                            // unflip
                            undo_last_flip();
                            undo_last_flip();
                            undo_last_flip();
                            assert(cost_before == total_cost());
                        }
                    }
                }

                unmark_edge_added(a1, b);
                unmark_edge_deleted(b, b1);
            }

            unmark_edge_added(s1, a);
            unmark_edge_deleted(a, a1);
        }
        return false;
    }

    Cost bit_dfs(int v, int bit, vector<vector<Cost>> &memo, vector<vector<int>> &best_next) {
        if (bit == (1 << n) - 1) {
            return G[v][0];
        }
        if (memo[bit][v] != -1) return memo[bit][v];

        memo[bit][v] = numeric_limits<Cost>::max();
        for (int i = 0; i < n; i++) {
            if ((bit >> i) & 1) continue;
            Cost value = G[v][i] + bit_dfs(i, bit | (1 << i), memo, best_next);
            if (value < memo[bit][v]) {
                memo[bit][v] = value;
                best_next[bit][v] = i;
            }
        }
        return memo[bit][v];
    }

public:
    LinKernighan(vector<int> &vs, Matrix<Cost> &G_, int seed) : tour(vs), mt(seed) {
        assert(vs[0] == 0);
        G = G_;
        n = G.size();

        neighbors.assign(n, vector<int>(n - 1));
        for (int i = 0; i < n; i++) {
            for (int j = 0, k = 0; j < n; j++) {
                if (j == i) continue;
                neighbors[i][k++] = j;
            }
            sort(neighbors[i].begin(), neighbors[i].end(), [&](int a, int b) { return G[i][a] < G[i][b]; });
        }

        is_added.assign(n, vector<bool>(n, false));
        is_deleted.assign(n, vector<bool>(n, false));
    }

    vector<int> find_tour() {
        if (n <= 10) {
            vector<vector<Cost>> memo(1 << n, vector<Cost>(n, -1));
            vector<vector<int>> best_next(1 << n, vector<Cost>(n, -1));
            bit_dfs(0, 1, memo, best_next);
            int v = 0, bit = 1;
            vector<int> ret = {v};
            for (int i = 1; i < n; i++) {
                v = best_next[bit][v];
                bit |= (1 << v);
                ret.push_back(v);
            }
            tour = ArrayTour(ret);
            return ret;
        }
        int stall_count = n;
        int repeat_count = min(1000, n);
        stall_count = 2000;
        repeat_count = 2000;
        chained_lin_kernighan(stall_count, repeat_count);
        cerr << total_cost() << endl;
        return tour.get_tour_from();
    }
};


// Union Find from toolkit/common/
struct UnionFind {

    std::vector<int> M_par;
    std::vector<int> M_rank;
    std::vector<int> M_size;

private:
    void init(int n = 1) {
        M_par.resize(n);
        M_rank.resize(n);
        M_size.resize(n);
        for (int i = 0; i < n; i++) {
            M_par[i] = i;
            M_rank[i] = 0;
            M_size[i] = 1;
        }
    }

public:

    UnionFind(size_t n = 1) {
        init(n);
    }

    size_t find(size_t x) {
        if (M_par[x] == x) return x;
        size_t r = find(M_par[x]);
        return M_par[x] = r;
    }

    bool same(size_t x, size_t y) {
        return find(x) == find(y);
    }

    bool unite(size_t x, size_t y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        if (M_rank[x] < M_rank[y]) std::swap(x, y);
        if (M_rank[x] == M_rank[y]) M_rank[x]++;
        M_par[y] = x;
        M_size[x] = M_size[x] + M_size[y];
        return true;
    }

    size_t size(size_t x) {
        return M_size[find(x)];
    }

};


constexpr int INF = 1e9;
constexpr int num_groups = 2;

int V, E;
constexpr int V_max = 400;
Matrix<int> G_all;
Matrix<set<int>> successors;
constexpr int T_max = 10000;
constexpr int T_last = 9500;

vector<int> solve_tsp(vector<int> &vs) {
    if (vs.size() <= 3) {
        return vs;
    }
    int n = vs.size();
    vector<int> tour(n);
    iota(tour.begin(), tour.end(), 0);
    Matrix<int> G(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            G[i][j] = G_all[vs[i]][vs[j]];
        }
    }
    LinKernighan<int> lk(tour, G, 0);
    tour = lk.find_tour();
    vector<int> ret(n);
    for (int i = 0; i < n; i++) {
        ret[i] = vs[tour[i]];
    }
    return ret;
}

int update_group_in_subtree(int v, int par, int k, vector<vector<int>>& tree, vector<int>& group_of){
    int subtree_size = 1;
    for(int to : tree[v]){
        if(to != par && group_of[to] == group_of[v]){
            subtree_size += update_group_in_subtree(to, v, k, tree, group_of);
        }
    }
    group_of[v] = k;
    return subtree_size;
}

vector<int> split_into_groups(int V, vector<tuple<int, int, int>> &edges) {
    vector<vector<int>> tree(V);
    {
        // build minimum spanning tree
        sort(edges.begin(), edges.end());
        UnionFind uf(V);
        for (auto &edge : edges) {
            int d, u, v;
            tie(d, u, v) = edge;
            if (uf.unite(u, v)) {
                tree[u].push_back(v);
                tree[v].push_back(u);
            }
        }
    }

    vector<pair<int, int>> best_split;
    vector<int> group_of(V, 0);
    vector<int> group_size = {V};
    for(int k=1;k<=num_groups - 1;k++){
        int best_diff = V;
        pair<int, int> best_split;
        for(int i=0;i<V;i++) {
            for (int j : tree[i]) {
                if(j <= i) continue;  // check them once
                if(group_of[i] != group_of[j]) continue;
                // split tree by removing the edge between i1 and j1
                int subtree_size = update_group_in_subtree(i, j, k, tree, group_of);
                group_size.push_back(subtree_size);
                group_size[group_of[j]] -= subtree_size;

                int diff = (*max_element(group_size.begin(), group_size.end())) - (*min_element(group_size.begin(), group_size.end()));
                if(diff < best_diff){
                    best_diff = diff;
                    best_split = make_pair(i, j);
                }

                group_size[group_of[j]] += subtree_size;
                group_size.pop_back();
                // undo updating groups
                update_group_in_subtree(i, j, group_of[j], tree, group_of);
            }
        }
        int i = best_split.first;
        int j = best_split.second;
        update_group_in_subtree(i, j, k, tree, group_of);
    }

    return group_of;
}


int count_num_of_paths(int i, int j) {
    if (i == j) {
        return 1;
    }
    int cnt = 0;
    for (int k : successors[i][j]) {
        cnt += count_num_of_paths(k, j);
    }
    return cnt;
}


void warshall_floyd() {
    successors.assign(V, vector<set<int>>(V));
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            successors[i][j].insert(j);
        }
    }
    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                int nc = G_all[i][k] + G_all[k][j];
                if (nc >= INF) continue;
                if (nc < G_all[i][j]) {
                    G_all[i][j] = nc;
                    successors[i][j].clear();
                    successors[i][j] = successors[i][k];
                } else if (nc == G_all[i][j]) {
                    for (int ni : successors[i][k]) {
                        successors[i][j].insert(ni);
                    }
                }
            }
        }
    }

    int num_paths = 0;
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            num_paths += count_num_of_paths(i, j);
        }
    }
    cerr << "num_paths: " << num_paths << endl;
    cerr << "mean: " << double(num_paths) / (V * V) << endl;
}


struct Order {
public:
    int dst;
    int t;
    int order_id;
    bool done;

    Order() : dst(-1), t(-1), order_id(-1), done(false) {}

    Order(int dst_, int t_, int order_id_) : dst(dst_), t(t_), order_id(order_id_), done(false) {}

    bool is_initialized() {
        return dst > 0;
    }

};


Order order_from_id[T_max];
vector<set<int>> carrying_order_ids_to;
vector<int> carrying_order_num;


struct PeakTimeEstimator{
private:
    int t;
    int n;
    vector<int> T_peak_candidates;
    vector<double> likelihoods;

public:
    int T_peak;

    PeakTimeEstimator(int start=1, int end=T_last, int step=5){
        T_peak = T_last / 2;
        t = 0;

        for(int i=start;i<end;i+=step){
            T_peak_candidates.push_back(i);
        }
        n = T_peak_candidates.size();
        likelihoods.assign(n, 0);
    }

    void add_observation(bool new_order_found){
        for(int i=0;i<n;i++){
            int T_peak_cand = T_peak_candidates[i];
            double p_order;
            if(t < T_peak_cand){
                p_order = double(t) / T_peak_cand;
            }else if(t < T_last){
                p_order = double(T_last - t) / (T_last - T_peak_cand);
            }else{
                p_order = 0;
            }
            if(new_order_found){
                likelihoods[i] += log(p_order);
            }else{
                likelihoods[i] += log(1 - p_order);
            }
        }
        int max_i = distance(likelihoods.begin(), max_element(likelihoods.begin(), likelihoods.end()));
        T_peak = T_peak_candidates[max_i];
        t++;
    }
};


vector<int> best_path_detail;
int_fast64_t best_path_score;

void find_best_path_detail(int i, int j, int t, int_fast64_t score, vector<int> &vs, bitset<V_max> &visited) {
    if (i == j) {
        if (score > best_path_score) {
            best_path_score = score;
            best_path_detail = vs;
        }
        return;
    }
    for (int k : successors[i][j]) {
        bool backup = visited[k];
        if (!visited[k] && t <= T_max) {
            for (int order_id : carrying_order_ids_to[k]) {
                auto &order = order_from_id[order_id];
                assert(order.is_initialized() && !order.done);
                score += int_fast64_t(T_max) * T_max - int_fast64_t(t - order.t) * (t - order.t);
                assert(T_max * T_max - (t - order.t) * (t - order.t) > 0);
            }
            visited[k] = true;
        }
        vs.push_back(k);

        find_best_path_detail(k, j, t + G_all[i][k], score, vs, visited);

        vs.pop_back();
        visited[k] = backup;
    }
}

struct AgentState {
public:
    bool on_tsp;
    int cur_v, tour_index_next, rest_distance, next_dst;
    vector<int> actual_tour;

    AgentState() {
        on_tsp = false;
    }

    int_fast64_t plan(vector<int> &vs, int t_start, bool back_to_home=true) {
        if(!back_to_home){
            vs.push_back(V);
            vs.push_back(V + 1);
        }
        vector<int> tour = solve_tsp(vs);
        assert(tour[0] == 0);
        tour.push_back(0);
        assert(tour.size() >= 3);

        if(!back_to_home){
            if(tour[1] == V){
                assert(tour[2] == V + 1);
                reverse(tour.begin(), tour.end());
            }
            assert(tour[tour.size() - 2] == V);
            assert(tour[tour.size() - 3] == V + 1);
            tour.pop_back();  // pop tailing zero
            tour.pop_back();  // pop V
            tour.pop_back();  // pop V + 1
            tour.push_back(0);
        }

        int t_end = 0;

        int_fast64_t total_score = 0;
        vector<int> actual_forward_tour;
        {
            int t = t_start;
            bitset<V_max> visited;
            for (int pos = 1; pos < tour.size(); pos++) {
                int i = tour[pos - 1];
                int j = tour[pos];

                best_path_score = -1;
                vector<int> vs;
                find_best_path_detail(i, j, t, 0, vs, visited);
                assert(best_path_score >= 0);

                for (int k : best_path_detail) {
                    actual_forward_tour.push_back(k);
                    visited[k] = true;
                }

                total_score += best_path_score;
                assert(total_score >= 0);
                t += G_all[i][j];
            }
            t_end = t;
        }

        int_fast64_t total_score_backward = 0;
        vector<int> actual_backward_tour;
        {
            int t = t_start;
            bitset<V_max> visited;
            for (int pos = tour.size() - 2; pos >= 0; pos--) {
                int i = tour[pos + 1];
                int j = tour[pos];

                best_path_score = -1;
                vector<int> vs;
                find_best_path_detail(i, j, t, 0, vs, visited);
                assert(best_path_score >= 0);

                for (int k : best_path_detail) {
                    actual_backward_tour.push_back(k);
                    visited[k] = true;
                }

                total_score_backward += best_path_score;
                t += G_all[i][j];
            }
            assert(t == t_end);
        }

        if(T_max < t_end && back_to_home){
            int_fast64_t total_score_non_returning = plan(vs, t_start, false);
            if(total_score_non_returning > max(total_score, total_score_backward)){
                return total_score_non_returning;
            }
        }

        if (total_score > total_score_backward) {
            actual_tour = actual_forward_tour;
        } else {
            actual_tour = actual_backward_tour;
        }

        on_tsp = true;
        cur_v = 0;
        tour_index_next = 0;
        next_dst = actual_tour[tour_index_next];
        rest_distance = G_all[cur_v][next_dst];

        return max(total_score_backward, total_score);
    }

    void step() {
        assert(on_tsp);
        assert(rest_distance >= 1);
        cout << next_dst + 1 << endl;
        rest_distance -= 1;

        if (rest_distance == 0) {
            cur_v = next_dst;
            tour_index_next++;
            if (tour_index_next == actual_tour.size()) {
                assert(cur_v == 0);
                on_tsp = false;
            } else {
                next_dst = actual_tour[tour_index_next];
                rest_distance = G_all[cur_v][next_dst];
            }
        }
    }

    bool need_planning() {
        return (!on_tsp) || (cur_v == 0 && rest_distance == G_all[cur_v][next_dst] && tour_index_next != 0);
    }
};

int main() {
#ifdef DEBUG
    ifstream cin("/home/chubachi/workspace/atcoder/hokudai-hitachi2019-1/solution/judge_example_01.txt");
#endif

    // recieve |V| and |E|
    cin >> V >> E;

    G_all.assign(V, vector<int>(V, INF));
    vector<tuple<int, int, int>> edges(E);
    for (int i = 0; i < E; i++) {
        // recieve edges
        int u, v, d;
        cin >> u >> v >> d;
        u--;
        v--;
        G_all[u][v] = d;
        G_all[v][u] = d;
        edges[i] = make_tuple(d, u, v);
    }

    // recieve freqencies
    vector<int> freq(V);
    for (int i = 0; i < V; i++) cin >> freq[i];
    {
        int T_max_;
        cin >> T_max_;
        assert(T_max == T_max_);
    }

    // split the graph into two
    auto group_of = split_into_groups(V, edges);

    // pre-compute min cost path
    warshall_floyd();

    // add two nodes for non-returning tour
    for(auto& g_sub : G_all){
        g_sub.push_back(INF);
        g_sub.push_back(INF);
    }
    G_all.emplace_back(V + 2, INF);
    G_all.emplace_back(V + 2, INF);
    G_all[V][0] = 0;
    G_all[0][V] = 0;
    G_all[V][V + 1] = 0;
    G_all[V + 1][V] = 0;
    for(int i=1;i<V;i++){
        G_all[V + 1][i] = 0;
        G_all[i][V + 1] = 0;
    }

    carrying_order_ids_to.assign(V, {});
    carrying_order_num.assign(num_groups, 0);

    AgentState agent_state;
    PeakTimeEstimator peak_time_estimator;
    int_fast64_t current_score = 0;

    for (int t = 0; t < T_max; t++) {

        if((t + 1) % 100 == 0){
            cerr << current_score << endl;
        }

        // the number of new order
        int N_new;
        cin >> N_new;
        for (int j = 0; j < N_new; j++) {
            int new_id, dst;
            cin >> new_id >> dst;
            new_id--;
            dst--;
            assert(new_id < T_max);  // id < T_last < T_max
            assert(!order_from_id[new_id].is_initialized());
            order_from_id[new_id] = Order(dst, t, new_id);
        }

        peak_time_estimator.add_observation(N_new > 0);
        if((t + 1) % 1000 == 0){
            cerr << "T_peak: " << peak_time_estimator.T_peak << endl;
        }

        // the number of items transferred into the car at time t.
        int N_put;
        cin >> N_put;
        for (int j = 0; j < N_put; j++) {
            int put_id;
            cin >> put_id;
            put_id--;
            assert(put_id < T_max);  // id < T_last < T_max
            auto &order = order_from_id[put_id];
            assert(order.is_initialized());
            assert(!order.done);
            carrying_order_ids_to[order.dst].insert(put_id);
            carrying_order_num[group_of[order.dst]]++;
        }

        // Plan next TSP
        if (agent_state.need_planning()) {
            int max_group = distance(carrying_order_num.begin(),
                                     max_element(carrying_order_num.begin(), carrying_order_num.end()));
            if (carrying_order_num[max_group] > 0) {
                vector<int> vs;
                vs.push_back(0);
                for (int v = 1; v < V; v++) {
                    if (group_of[v] == max_group && !carrying_order_ids_to[v].empty()) {
                        vs.push_back(v);
                    }
                }
                agent_state.plan(vs, t);
            }
        }

        if (agent_state.on_tsp) {
            agent_state.step();
        } else {
            cout << -1 << endl; // stay
        }

        string verdict;
        cin >> verdict;
        if (verdict == "NG") {
            return 1;
        }

        // the number of orders that have been delivered at time t.
        int N_achive;
        cin >> N_achive;
        for (int j = 0; j < N_achive; j++) {
            int achive_id;
            cin >> achive_id;
            achive_id--;
            assert(achive_id < T_max);  // id < T_last < T_max
            auto &order = order_from_id[achive_id];
            assert(order.is_initialized());
            assert(!order.done);
            order.done = true;
            carrying_order_ids_to[order.dst].erase(achive_id);
            carrying_order_num[group_of[order.dst]]--;

            current_score += T_max * T_max - (t + 1 - order.t) * (t + 1 - order.t);
        }
    }

    int done_num = 0, order_num = 0;
    for (auto &order : order_from_id) {
        if (!order.is_initialized()) continue;
        order_num++;
        if (order.done) done_num++;
    }
    cerr << order_num << " " << done_num << endl;
    cerr << current_score << endl;

    return 0;
}

Measured memory_bytes: 21284