OIG XVII - dra

// https://szkopul.edu.pl/problemset/problem/fruIsNUEEMImq5XioKRRIgu_/site/?key=statement
// OIJ XVII 2 etap

#include <bits/stdc++.h>

using namespace std;

constexpr int sizik = 3 * 100 * 1001;

int deg[sizik];

std::vector<int> kra[sizik];
int ans[sizik];
std::bitset<sizik> vis;

int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    int n, m;
    std::cin >> n >> m;

    if (n % 2 == 1) {
        std::cout << "NIE\n";
        return 0;
    }

    if (m != 3 * (n / 2) - 4) {
        std::cout << "NIE\n";
        return 0;
    }

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

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

        deg[a]++;
        deg[b]++;
    }

    bool flag = true;

    int c1 = 0, c3 = 0;

    std::vector<int> odr;

    for (int i = 1; i <= n; i++) {
        if (deg[i] == 1) {
            c1++;
            odr.push_back(i);
        } else if (deg[i] == 3) {
            c3++;
        } else {
            flag = false;
            break;
        }
    }

    if (!flag || c1 != 4) {
        std::cout << "NIE\n";
        return 0;
    }

    int ob = 1;

    for (int i = 1; i <= 3; i++) {
        flag = false;

        for (const auto& r : kra[kra[odr[i]][0]]) {
            if (r == kra[odr[0]][0]) {
                flag = true;
            }
        }

        if (flag == true) {
            ob = i;
        }
    }

    ans[1] = odr[0];
    ans[2] = odr[ob];

    int par1 = odr[0], par2 = odr[ob];
    int ch1 = kra[par1][0], ch2 = kra[par2][0];

    vis[par1] = true;
    vis[par2] = true;

    for (int i = 2; 2 * i <= n; i++) {
        ans[2 * i - 1] = ch1;
        ans[2 * i] = ch2;

        vis[ch1] = true;
        vis[ch2] = true;

        par1 = ch1;
        par2 = ch2;

        for (const auto& u : kra[ch1]) {
            if (!vis[u]) {
                ch1 = u;
                break;
            }
        }

        for (const auto& u : kra[ch2]) {
            if (!vis[u]) {
                ch2 = u;
                break;
            }
        }
    }

    std::vector<bool> visited(n + 1);

    for (int i = 1; i <= n; i++) {
        visited[ans[i]] = true;
    }

    bool isGood = true;

    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            isGood = false;
            break;
        }
    }

    if (!isGood) {
        std::cout << "NIE\n";
        return 0;
    }

    std::cout << "TAK\n";
    for (int i = 1; 2 * i <= n; i++) {
        std::cout << ans[2 * i - 1] << " " << ans[2 * i] << '\n';
    }

    return 0;
}