YZOJ P2966 染色
时间限制:2000MS 内存限制:131072KB
难度:\(7.0\)
-
题目描述
你有 \(n\) 只猫,每一只猫认识另一些猫。但若 \(a\) 猫认识 \(b\) 猫,\(b\) 猫不一定会认识 \(a\) 猫。
现在,你需要将每一只猫染成红色或绿色。你是否可以通过染色让每一只猫都认识偶数只和自己同色的猫呢?
-
输入格式
第一行 \(n\);
接下来 \(n\) 行,每行第一个数 \(d_i\) 表示猫 \(i\) 认识的猫的个数,后面跟着 \(d_i\) 个数表示认识的猫是哪些。
-
输出格式
达不到要求,输出 Impossible
。
否则第一行输出红色猫的个数,第二行输出哪些猫是红色(那么其他猫就是绿色)
可以输出任意方案。
-
样例输入
1 2 3 4 5 6 |
5 3 2 3 4 2 1 3 4 2 1 4 5 2 1 3 1 3 |
-
样例输出
1 2 |
3 1 2 3 |
-
数据规模与约定
对于 \(100\%\) 的数据,\(n \leq 2000\) 。