三分图染色

题目描述

给定一个三分图，有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，你可以以任意顺序输出任意解

样例

提示

三个点集分别是{1,2}{3,4}{5,6}

3 \leq n \leq 100,3 \leq m \leq 1000, m * n \leq 30000 。保证输入的图至少有一个解

来源

模板