OI XXXII - red

// https://szkopul.edu.pl/problemset/problem/8nZ0jURcTr-O3V0ASzQJOCpy/site/?key=statement

#include <bits/stdc++.h>

// #define GARY_DBG
#define GARY_LIB

constexpr int sizik = 1000 * 1001;

#define ar std::array

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

struct Trio {
    int a, b, i;
};
std::vector<Trio> kra;

namespace dsu {

int rep[sizik], sz[sizik];

void init(int n) {
    for (int i = 1; i <= n; i++) {
        rep[i] = i;
    }
}

int Find(int a) {
    int root = a;
    while (rep[root] != root)
        root = rep[root];
    while (rep[a] != root) {
        int next = rep[a];
        rep[a] = root;
        a = next;
    }
    return root;
}

void Union(int a, int b) {
    a = Find(a), b = Find(b);

    if (a != b) {
        if (sz[a] < sz[b]) std::swap(a, b);
        rep[b] = a;
        sz[a] += sz[b];
    }
}

} // namespace dsu

int n, m;
int x;
void print_ans(const std::vector<int>& ans) {
    std::cout << "3 " << ans.size() << " ";
    for (const auto& a : ans) {
        std::cout << (int)a << " ";
    }
    std::cout << std::endl;
}

bool comp_niezalezne(const Trio& a, const Trio& b) {
    std::cout << "1 " << (int)a.i << " " << (int)b.i << std::endl;
    std::cin >> x;
    return x == -1;
}

bool comp_gwiazda(const Trio& a, const Trio& b) {
    std::cout << "2 2 " << (int)a.i << " " << (int)b.i << std::endl;
    std::cin >> x;
    return x == a.i;
}

bool comp(const Trio& a, const Trio& b) {
    if (a.a == b.a || a.a == b.b || a.b == b.a || a.b == b.b) {
        return comp_gwiazda(a, b);
    } else {
        return comp_niezalezne(a, b);
    }
}

int check(int idx1, int idx2) {
    if (kra[idx1].a == kra[idx2].a || kra[idx1].a == kra[idx2].b) {
        return kra[idx1].a;
    }
    if (kra[idx1].b == kra[idx2].a || kra[idx1].b == kra[idx2].b) {
        return kra[idx1].b;
    }
    return false;
}

int check_center(int idx1, int center) {
    return kra[idx1].a == center || kra[idx1].b == center;
}

void solve() {
    std::cin >> n >> m;
    kra.resize(m);
    int curr = 0;
    for (auto& [a, b, i] : kra) {
        std::cin >> a >> b;
        i = curr++;
        a++, b++;
        if (a > b) std::swap(a, b);
    }

    using dsu::init, dsu::Find, dsu::Union;

    init(n);

    std::vector<int> ans;
    ans.reserve(n);

    while (true) {
        std::set<int> ziomy;
        for (int i = 1; i <= n; i++) {
            if (Find(i) == i) {
                ziomy.insert(i);
            }
        }

        if (ziomy.size() <= 1) break;

        std::map<int, std::vector<int>> p;

        std::vector<int> to_del;

        for (int i = 0; i < (int)kra.size(); i++) {
            if (Find(kra[i].a) == Find(kra[i].b)) {
                to_del.push_back(i);
                continue;
            }
            p[Find(kra[i].a)].push_back(i);
            p[Find(kra[i].b)].push_back(i);
        }

        while (ziomy.size() > 1) {
            int v = *ziomy.begin();

            auto pv = p[v];
            std::vector<int> core;
            int center = 0;
            int i = 0;
            while (i < (int)pv.size()) {
                if (core.empty()) {
                    core.push_back(pv[i]);
                    i++;
                } else if (core.size() == 1) {
                    int possible_center = check(pv[i], core[0]);

                    if (possible_center != 0) {
                        center = possible_center;
                        core.push_back(pv[i]);
                        i++;
                    } else {
                        if (comp_niezalezne(kra[pv[i]], kra[core[0]])) {
                            core.pop_back();
                            center = 0;
                        } else {
                            i++;
                        }
                    }
                } else {
                    if (check_center(pv[i], center)) {
                        core.push_back(pv[i]);
                        i++;
                    } else {
                        int conflict_idx = -1;

                        for (int k = 0; k < (int)core.size() && k < 3; k++) {
                            if (check(pv[i], core[k]) == 0) {
                                conflict_idx = k;
                                break;
                            }
                        }
                        if (conflict_idx == -1) {
                            i++;
                        } else {
                            if (comp_niezalezne(kra[pv[i]], kra[core[conflict_idx]])) {
                                core[conflict_idx] = core.back();
                                core.pop_back();

                                if (core.size() < 2) {
                                    center = 0;
                                }
                            } else {
                                i++;
                            }
                        }
                    }
                }
            }

            assert(!core.empty());
            int good_idx = core[0];
            int w = kra[good_idx].i;
            if (core.size() > 1) {
                std::cout << "2 " << core.size() << " ";
                for (const auto& o : core) {
                    std::cout << kra[o].i << " ";
                }
                std::cout << std::endl;
                std::cin >> w;
                for (const auto& o : core) {
                    if (kra[o].i == w) {
                        good_idx = o;
                        break;
                    }
                }
            }
            ans.push_back(w);

            to_del.push_back(good_idx);
            ziomy.erase(v);
            int u = kra[good_idx].a;
            if (Find(u) == Find(v)) u = kra[good_idx].b;
            ziomy.erase(Find(u));

            Union(u, v);
        }

        std::sort(to_del.begin(), to_del.end(), std::greater<int>());
        for (const auto& idx : to_del) {
            if (idx < kra.size()) {
                std::swap(kra[idx], kra.back());
                kra.pop_back();
            }
        }
    }

    print_ans(ans);
}

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