#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9 + 7;
const int MAXN = 2005;
int n, m, k, dd;
vi G[MAXN];
bool vis[MAXN];
vi big;
vi ans;
void input() {
int x, y;
cin >> n >> m >> k;
for (int i = 0; i < m; i++) {
cin >> x >> y;
G[x].PB(y);
G[y].PB(x);
}
}
int deg(int v) {
set<int> ms;
for (int u : ans) {
ms.insert(u);
}
if (ms.count(v)) {
return 0;
}
int degree = 0;
for (int u : G[v]) {
if (ms.count(u) == 0) {
degree++;
}
}
return degree;
}
bool areDegreeGood() {
set<int> ms;
for (int u : ans) {
ms.insert(u);
}
for (int i = 1; i <= n; i++) {
if (ms.count(i)) {
continue;
}
int degree = 0;
for (int u : G[i]) {
if (ms.count(u) == 0) {
degree++;
if (degree > 2) {
return false;
}
}
}
}
return true;
}
void dfs(int v, int parent = -1) {
vis[v] = true;
for (int u : G[v]) {
if (u == parent || vis[u]) {
continue;
}
dfs(u, v);
}
}
vi getCycles() {
for (int i = 1; i <= n; i++) {
vis[i] = false;
}
for (int u : ans) {
vis[u] = true;
}
for (int i = 1; i <= n; i++) {
int d = deg(i);
set<int> ms;
for (int u : ans) {
ms.insert(u);
}
if (d <= 1 && ms.count(i) == 0) {
vis[i] = true;
dfs(i);
}
}
vi onCycles;
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
onCycles.PB(i);
dfs(i);
}
}
return onCycles;
}
void output() {
cout << "TAK\n";
cout << ans.size() << "\n";
for (int u : ans) {
cout << u << " ";
}
cout << "\n";
exit(0);
}
void licz(int ile) {
if (areDegreeGood()) {
vi cycles = getCycles();
if ((int)cycles.size() <= ile) {
for (int u : cycles) {
ans.PB(u);
}
output();
}
}
if (ile == 0) {
return;
}
for (int i: big) {
if (deg(i) > 2) {
ans.PB(i);
licz(ile - 1);
ans.pop_back();
int possible = 3;
set<int> ms;
for (int u: ans) {
ms.insert(u);
}
for (int u = 0; possible; u++) {
ans.PB(G[i][u]);
licz(ile - 1);
ans.pop_back();
if (ms.count(G[i][u]) == 0) {
possible--;
}
}
break;
}
}
}
void solve() {
for (int i = 1; i <= n; i++) {
if (deg(i) > 2) {
big.PB(i);
}
}
licz(k);
cout << "NIE\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
input();
solve();
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgUEIgcHVzaF9iYWNrCiNkZWZpbmUgTVAgbWFrZV9wYWlyCiNkZWZpbmUgRiBmaXJzdAojZGVmaW5lIFMgc2Vjb25kCnR5cGVkZWYgbG9uZyBsb25nIGxsOwp0eXBlZGVmIHZlY3RvcjxpbnQ+IHZpOwp0eXBlZGVmIHBhaXI8aW50LCBpbnQ+IHBpaTsKdHlwZWRlZiBwYWlyPGxsLCBsbD4gcGxsOwpjb25zdCBpbnQgSU5GID0gMWU5ICsgNzsKY29uc3QgaW50IE1BWE4gPSAyMDA1OwogCmludCBuLCBtLCBrLCBkZDsKdmkgR1tNQVhOXTsKYm9vbCB2aXNbTUFYTl07CnZpIGJpZzsKCnZpIGFuczsKIAp2b2lkIGlucHV0KCkgewogICAgICAgIGludCB4LCB5OwogICAgICAgIGNpbiA+PiBuID4+IG0gPj4gazsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IG07IGkrKykgewogICAgICAgICAgICAgICAgY2luID4+IHggPj4geTsKICAgICAgICAgICAgICAgIEdbeF0uUEIoeSk7CiAgICAgICAgICAgICAgICBHW3ldLlBCKHgpOwogICAgICAgIH0KfQogCmludCBkZWcoaW50IHYpIHsKICAgICAgICBzZXQ8aW50PiBtczsKICAgICAgICBmb3IgKGludCB1IDogYW5zKSB7CiAgICAgICAgICAgICAgICBtcy5pbnNlcnQodSk7CiAgICAgICAgfQogICAgICAgIGlmIChtcy5jb3VudCh2KSkgewogICAgICAgICAgICAgICAgcmV0dXJuIDA7CiAgICAgICAgfQogICAgICAgIGludCBkZWdyZWUgPSAwOwogICAgICAgIGZvciAoaW50IHUgOiBHW3ZdKSB7CiAgICAgICAgICAgICAgICBpZiAobXMuY291bnQodSkgPT0gMCkgewogICAgICAgICAgICAgICAgICAgICAgICBkZWdyZWUrKzsKICAgICAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgcmV0dXJuIGRlZ3JlZTsKfQogCmJvb2wgYXJlRGVncmVlR29vZCgpIHsKICAgICAgICBzZXQ8aW50PiBtczsKICAgICAgICBmb3IgKGludCB1IDogYW5zKSB7CiAgICAgICAgICAgICAgICBtcy5pbnNlcnQodSk7CiAgICAgICAgfQogICAgICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IG47IGkrKykgewogICAgICAgICAgICAgICAgaWYgKG1zLmNvdW50KGkpKSB7CiAgICAgICAgICAgICAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgaW50IGRlZ3JlZSA9IDA7CiAgICAgICAgICAgICAgICBmb3IgKGludCB1IDogR1tpXSkgewogICAgICAgICAgICAgICAgICAgICAgICBpZiAobXMuY291bnQodSkgPT0gMCkgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGRlZ3JlZSsrOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmIChkZWdyZWUgPiAyKSB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICByZXR1cm4gZmFsc2U7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIHJldHVybiB0cnVlOwp9CiAKdm9pZCBkZnMoaW50IHYsIGludCBwYXJlbnQgPSAtMSkgewogICAgICAgIHZpc1t2XSA9IHRydWU7CiAgICAgICAgZm9yIChpbnQgdSA6IEdbdl0pIHsKICAgICAgICAgICAgICAgIGlmICh1ID09IHBhcmVudCB8fCB2aXNbdV0pIHsKICAgICAgICAgICAgICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBkZnModSwgdik7CiAgICAgICAgfQp9CiAKdmkgZ2V0Q3ljbGVzKCkgewogICAgICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IG47IGkrKykgewogICAgICAgICAgICAgICAgdmlzW2ldID0gZmFsc2U7CiAgICAgICAgfQogICAgICAgIGZvciAoaW50IHUgOiBhbnMpIHsKICAgICAgICAgICAgICAgIHZpc1t1XSA9IHRydWU7CiAgICAgICAgfQogICAgICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IG47IGkrKykgewogICAgICAgICAgICAgICAgaW50IGQgPSBkZWcoaSk7CiAgICAgICAgICAgICAgICBzZXQ8aW50PiBtczsKICAgICAgICAgICAgICAgIGZvciAoaW50IHUgOiBhbnMpIHsKICAgICAgICAgICAgICAgICAgICAgICAgbXMuaW5zZXJ0KHUpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgaWYgKGQgPD0gMSAmJiBtcy5jb3VudChpKSA9PSAwKSB7CiAgICAgICAgICAgICAgICAgICAgICAgIHZpc1tpXSA9IHRydWU7CiAgICAgICAgICAgICAgICAgICAgICAgIGRmcyhpKTsKICAgICAgICAgICAgICAgIH0KICAgICAgICB9CiAKICAgICAgICB2aSBvbkN5Y2xlczsKICAgICAgICBmb3IgKGludCBpID0gMTsgaSA8PSBuOyBpKyspIHsKICAgICAgICAgICAgICAgIGlmICghdmlzW2ldKSB7CiAgICAgICAgICAgICAgICAgICAgICAgIG9uQ3ljbGVzLlBCKGkpOwogICAgICAgICAgICAgICAgICAgICAgICBkZnMoaSk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgfQogCiAgICAgICAgcmV0dXJuIG9uQ3ljbGVzOwp9CiAKdm9pZCBvdXRwdXQoKSB7CiAgICAgICAgY291dCA8PCAiVEFLXG4iOwogICAgICAgIGNvdXQgPDwgYW5zLnNpemUoKSA8PCAiXG4iOwogICAgICAgIGZvciAoaW50IHUgOiBhbnMpIHsKICAgICAgICAgICAgICAgIGNvdXQgPDwgdSA8PCAiICI7CiAgICAgICAgfQogICAgICAgIGNvdXQgPDwgIlxuIjsKICAgICAgICBleGl0KDApOwp9CiAKdm9pZCBsaWN6KGludCBpbGUpIHsKICAgICAgICBpZiAoYXJlRGVncmVlR29vZCgpKSB7CiAgICAgICAgICAgICAgICB2aSBjeWNsZXMgPSBnZXRDeWNsZXMoKTsKICAgICAgICAgICAgICAgIGlmICgoaW50KWN5Y2xlcy5zaXplKCkgPD0gaWxlKSB7CiAgICAgICAgICAgICAgICAgICAgICAgIGZvciAoaW50IHUgOiBjeWNsZXMpIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBhbnMuUEIodSk7CiAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICAgICAgb3V0cHV0KCk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGlmIChpbGUgPT0gMCkgewogICAgICAgICAgICAgICAgcmV0dXJuOwogICAgICAgIH0KIAogICAgICAgIGZvciAoaW50IGk6IGJpZykgewogICAgICAgICAgICAgICAgaWYgKGRlZyhpKSA+IDIpIHsKICAgICAgICAgICAgICAgICAgICAgICAgYW5zLlBCKGkpOwogICAgICAgICAgICAgICAgICAgICAgICBsaWN6KGlsZSAtIDEpOwogICAgICAgICAgICAgICAgICAgICAgICBhbnMucG9wX2JhY2soKTsKICAgICAgICAgICAgICAgICAgICAgICAgaW50IHBvc3NpYmxlID0gMzsKICAgICAgICAgICAgICAgICAgICAgICAgc2V0PGludD4gbXM7CiAgICAgICAgICAgICAgICAgICAgICAgIGZvciAoaW50IHU6IGFucykgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIG1zLmluc2VydCh1KTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgICAgICAgICBmb3IgKGludCB1ID0gMDsgcG9zc2libGU7IHUrKykgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGFucy5QQihHW2ldW3VdKTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBsaWN6KGlsZSAtIDEpOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGFucy5wb3BfYmFjaygpOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmIChtcy5jb3VudChHW2ldW3VdKSA9PSAwKSB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHBvc3NpYmxlLS07CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgfQp9CiAKdm9pZCBzb2x2ZSgpIHsKICAgICAgICBmb3IgKGludCBpID0gMTsgaSA8PSBuOyBpKyspIHsKICAgICAgICAgICAgaWYgKGRlZyhpKSA+IDIpIHsKICAgICAgICAgICAgICAgIGJpZy5QQihpKTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBsaWN6KGspOwogICAgICAgIGNvdXQgPDwgIk5JRVxuIjsKfQogCmludCBtYWluKCkgewogICAgICAgIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oMCk7CiAgICAgICAgY2luLnRpZShOVUxMKTsKICAgICAgICBjb3V0LnRpZShOVUxMKTsKIAogICAgICAgIGlucHV0KCk7CiAgICAgICAgc29sdmUoKTsKIAogICAgICAgIHJldHVybiAwOwp9