2649 - riddle

有n个点，m条边，k个非空的点的集合A1..Ak，满足每个点属于且仅属于一个集合。 现在要在每个集合中选恰好一个点，使得对于每一条边，两个端点中至少有一个被选择。

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个数字，表示每个集合中选择的点。

Examples

Input

样例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

Output


                


                
                            

        


        
            

            

        

            
            

                
                

                    Time Limit
                    
                        1 second                    
                

                

                    Memory Limit
                    128 MB
                

                
            

        


        


                 Stats
        


         上一题
        下一题