9314 - 三分图染色
时间限制 : 3 秒
内存限制 : 128 MB
给定一个三分图,有n个点m条边,求出三分图内的三个点集
G=(V,E)是一个无向图,如果顶点V可分割为三个互不相交的子集(A,B,C),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(比如:i \in A,j \in B),则称图G为一个三分图。
输入
第一行包含两个正整数n,m
接着m行,每行2个整数u,v。表示两者之间有一条边
输出
输出3行数字,分别表示点集。
每行数字第一个数字表示点集内的节点数量。接着再输出节点编号
本题包含SPJ,你可以以任意顺序输出任意解
样例
输入
6 7 1 5 2 3 4 6 1 6 3 5 3 6 2 4
输出
2 1 2 2 3 4 2 5 6
提示
三个点集分别是{1,2}{3,4}{5,6}
3 \leq n \leq 100,3 \leq m \leq 1000, m * n \leq 10000 。保证输入的图至少有一个解
来源
模板