// https://szkopul.edu.pl/problemset/problem/Oys6jiVOIap59lYCHRwDMbNT/site/?/key=statement
// Gildie

#include <bits/stdc++.h>

using namespace std;

#define int long long

constexpr int sizik = 200 * 1001;

#define ar std::array
#define pr std::pair
#define vec std::vector

// #define GARY_DBG

typedef vec<vec<int>> _kra;

int visited[sizik];
std::vector<int> kra[sizik];
int kolor[sizik];

// helper func
int rev(int c) {
    if (c == 1)
        return 2;
    else
        return 1;
}

bool BFS(int start) {
    // [v, color]
    std::queue<std::pair<int, int>> q;
    q.push({start, 1});

    int num = 0;
    std::vector<int> vertices;

    while (!q.empty()) {
        const auto [v, c] = q.front();
        q.pop();

        if (visited[v]) continue;
        visited[v] = true;
        num++;
        vertices.push_back(v);
        kolor[v] = c;

        for (const auto& u : kra[v]) {
            q.push({u, rev(c)});
        }
    }

    if (num <= 1) return false;

    bool isGood1 = true;
    for (const auto& a : vertices) {
        bool isGood = false;
        for (const auto& u : kra[a]) {
            if (kolor[u] != kolor[a]) {
                isGood = true;
            }
        }
        isGood1 &= isGood;
    }

    return isGood1;
}

void solve() {
    int n, m;
    std::cin >> n >> m;

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

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

    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            bool x = BFS(i);
            if (!x) {
                std::cout << "NIE\n";
                return;
            }
        }
    }

    std::cout << "TAK\n";
    for (int i = 1; i <= n; i++) {
        if (kolor[i] == 1) {
            std::cout << "K\n";
        } else {
            std::cout << "S\n";
        }
    }
}

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

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}