#include<bits/stdc++.h>
using namespace std;
#define maxn 500005

int _n,_m,a,b,_cnt=1,_head[maxn],_cc,_ans[maxn],_dp[maxn],root;
struct pp{
	int v,nt;
}_rd[maxn*4];
bool _bj[maxn];
void add(int a,int b){
	_rd[++_cnt].v = b;
	_rd[_cnt].nt=_head[a];
	_head[a]=_cnt;
}

bool dfs(int now,int fa){
	if(_bj[now]==1){
		root = now;
		return 1;
	}
	_bj[now]=1;
	for(int i = _head[now];i;i=_rd[i].nt){
		int v = _rd[i].v;
		if(v!=fa){
			if(dfs(v,now))return 1;
		}
	}
	return 0;
}
bool js(int now,int fa){
	if(_bj[now]==1)return 1;
	_bj[now]=1;
	for(int i = _head[now];i;i=_rd[i].nt){
		int v = _rd[i].v;
		if(v!=fa){
			if(js(v,now)){
				_ans[++_cc]=i/2;
				return 1;
			}
		}
	}
	return 0;
}

void  dp(int now,int fa){
	_bj[now]=1;
	for(int i = _head[now];i;i=_rd[i].nt){
		int v = _rd[i].v;
		if(v!=fa){
			dp(v,now);
			if(!_dp[v])_ans[++_cc]=i/2,_dp[v]=1,_dp[now]^=1;
		}
	}
	return;
}


int main(){
//	freopen("trap.in","r",stdin);
	cin >> _n >> _m;
	for(int i = 1;i <= _m;i++){
		cin >> a >> b;
		add(a,b+_n);
		add(b+_n,a);
	}
	for(int i = 1;i <= _n;i++){
		if(!_bj[i])
		if(dfs(i,0)){
				cout << "TAK" << endl;
				memset(_bj,0,sizeof(_bj));
				js(root,0);
				cout << _cc << endl;
				for(int i = 1;i <= _cc;i++){
					cout <<_ans[i] << " ";
				}
				return 0;
		}
	}
	memset(_bj,0,sizeof(_bj));
	for(int i = 1;i <= _n;i++){
		if(!_bj[i]){
			dp(i,0);
			if(!_dp[i]){
				cout << "NIE" << endl;
				return 0;
			}
		}
	}
	cout << "TAK" << endl;
	cout << _cc << endl;
	for(int i = 1;i <= _cc;i++)cout <<_ans[i] << " ";
	return 0;
}