Riddle [A]

Memory limit: 128 MB

The evil sorceror Voldebyte has imprisoned the brave knight Bytter the Bold in his tower. As was his custom, Voldebyte promised to free Bytter when he solved one of his (unsolved as yet) riddles. Bytter, unfortunately, has managed to kill Voldebyte's pet dragon and came close to killing Voldebyte himself, so Voldebyte decided a really tough riddle was in order. This is the riddle posed by Voldebyte to Bytter:

Byteland is divided into counties, in which there are altogether towns. Additionally, some pairs of towns are connected by bidirectional roads. I would like to choose a town in each county to be its capital in such a way that for each road at least one of its endpoints is a capital town. Is this possible?

Help poor Bytter save himself and solve the riddle for him.

Input

In the first line of the standard input there are three integers: (), denoting the number of towns in Voldebyte's riddle, (), denoting the number of roads, and (), denoting the number of counties. The towns are numbered from to .

In the next lines there are pairs of integers , (, ), the -th pair denotes a road connecting towns and . No pair of towns is connected by more than one road.

In the next lines there are descriptions of subsequent counties. The -th line begins with an integer (), denoting the number of towns in the -th county. Then integers are given, denoting the (distinct) numbers of the towns in the -th county. The sum of all the numbers is equal to .

Output

If the solution to the riddle is negative, your program should write a single line containing the word NIE (i.e., no in Polish) to the standard output.

Otherwise, your program should write two lines. The first should contain the word TAK (i.e., yes in Polish), the second should describe the solution. The second line should contain exactly integers. The -th of these integers should be the number of the town, which should be selected as the capital of the -th county.

If there are multiple correct solutions, your program can output any of them.

Example

For the input data:

6 5 2
1 2
3 1
1 4
5 2
6 2
3 3 4 2
3 1 6 5

the correct result is:

TAK
2 1

while for the input data:

3 3 1
1 2
2 3
3 1
3 1 2 3

the correct result is:

NIE

Task authors: Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk.