#P2649. riddle

    ID: 1687 传统题 1000ms 128MiB 尝试: 29 已通过: 3 难度: 8 上传者: 标签>CF2500提高+/省选-顶点覆盖2-SAT蕴含图Kosaraju 算法SCC 判定可满足性相向双指针

riddle

题目描述

有 nn 个点, mm 条边, kk 个非空的点的集合 A1…AkA_1 \dots A_k,满足每个点属于且仅属于一个集合。

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

输入格式

第一行,n,m,kn,m,k。

下面 mm 行,每行两个整数,x,yx,y。1≤x,y≤n1 \leq x,y \leq n,x≠y x \neq y。

下面 kk 行,每行第一个整数 ww,表示该集合的大小,后面 ww 个整数,表示该集合的数。

输出格式

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

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

6 5 2
1 2
3 1
1 4
5 2
6 2
3 3 4 2
3 1 6 5
TAK
2 1
3 3 1
1 2
2 3
3 1
3 1 2 3
NIE

数据规模与约定

对于 100%100\% 的数据,1≤n≤1061 \leq n \leq 10^6,1≤m≤1061 \leq m \leq 10^6,1≤k≤n1 \leq k \leq n。