#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);
            cerr << "final cost:" << total_cost() << endl;
            return ret;
        }
        int stall_count = n;
        int repeat_count = min(1000, n);
        stall_count = 1000;
        repeat_count = 1000;
        chained_lin_kernighan(stall_count, repeat_count);
        cerr << "final cost:" << 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;

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

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;
}


vector<int> split_into_groups(int V, vector<tuple<int, int, int>>& edges){
    sort(edges.begin(), edges.end());
    UnionFind uf(V);
    vector<vector<int>> tree(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);
        }
    }

    int min_diff = V;
    pair<int, int> min_diff_edge(-1, -1);
    for(int i=0;i<V;i++){
        vector<int> subtree_sizes;
        for(int child : tree[i]){
            stack<pair<int, int>> vps;
            vps.emplace(child, i);

            int size = 0;
            while(!vps.empty()){
                size++;
                auto vp = vps.top();
                vps.pop();
                int v = vp.first;
                int p = vp.second;
                for(int v_child : tree[v]){
                    if(v_child == p) continue;
                    vps.emplace(v_child, v);
                }
            }
            subtree_sizes.push_back(size);
        }
        assert(!subtree_sizes.empty());
        int k = distance(subtree_sizes.begin(), max_element(subtree_sizes.begin(), subtree_sizes.end()));
        int diff = abs(V / 2 - subtree_sizes[k]);
        if(diff < min_diff){
            min_diff = diff;
            min_diff_edge = make_pair(i, tree[i][k]);
        }
    }

    assert(min_diff != V);
    assert(min_diff_edge.first != -1);

    vector<int> group_of(V, 0);
    {
        int cnt = 0;
        stack<pair<int, int>> vps;
        vps.emplace(min_diff_edge.second, min_diff_edge.first);

        while(!vps.empty()){
            auto vp = vps.top();
            vps.pop();
            int v = vp.first;
            int p = vp.second;
            group_of[v] = 1;
            cnt++;
            for(int v_child : tree[v]){
                if(v_child == p) continue;
                vps.emplace(v_child, v);
            }
        }

        assert(abs(V / 2 - cnt) == min_diff);
    }
    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;


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]){
            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;
    }

    void plan(vector<int>& vs, int t_start){
        vector<int> tour = solve_tsp(vs);
        assert(tour[0] == 0);
        tour.push_back(0);
        assert(tour.size() >= 3);

        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(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];
    }

    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();

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

    AgentState agent_state;

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

        // 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);
        }

        // 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]]--;
        }
    }

    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;

    return 0;
}

Measured memory_bytes: 20300