#2764. riddle

riddle

Description

有n个点,m条边,k个非空的点的集合A1..Ak,满足每个点属于且仅属于一个集合。

现在要在每个集合中选恰好一个点,使得对于每一条边,两个端点中至少有一个被选择。

Format

Input

第一行,n,m,k。

下面m行,每行两个整数,x, y。1<=x, y<=n, x!=y

下面k行,每行第一个整数w,表示该集合的大小,后面w个整数,表示该集合的数

1<=n<=1000000 1<=m<=1000000 1<=k<=n

Output

如果可以,第一行输出TAK,否则输出NIE。

如果可以,下面一行,输出k个数字,表示每个集合中选择的点。

Samples

样例1
输入
6 5 2
1 2
3 1
1 4
5 2
6 2
3 3 4 2
3 1 6 5

输出
TAK
2 1

样例2
输入
3 3 1
1 2
2 3
3 1
3 1 2 3

输出
NIE