package xj;
import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner;
public class RanColor1 { static int D, B,T; static int map[][]; static int color[]; static class Node { int x; }
static Node[] queue; static boolean flag;
public static void main(String[] args) throws FileNotFoundException { /* Scanner sc=new Scanner(System.in); */ Scanner sc = new Scanner(new File("src/RanColor")); T=0; while (sc.hasNext()) { D = sc.nextInt(); B = sc.nextInt(); map = new int[D + 1][D + 1]; color = new int[D+1];// 0,1W,2B queue=new Node[D]; /*if (D == 0 && B == 0) { break; }*/ for (int i = 0; i < B; i++) { int a = sc.nextInt(); int b = sc.nextInt(); map[a][b] = 1; map[b][a] = 1; } flag = true; T++; bfs(1); if (!flag) { System.out.println("#"+T+" "+"-1"); } else { int w=0; for (int i = 1; i < D+1; i++) { if(color[i]==1){w++;} } System.out.print("#"+T+" "+w); for (int i = 1; i < D+1; i++) { if(color[i]==1){System.out.print(" "+i);} } System.out.println(); }// 记得正确输出 } }
private static void bfs(int step) { int head = 0; int tail = 1; Node n1 = new Node(); n1.x = step; queue[head] = n1; color[step] = 1; while(head<tail){ for (int i = 1; i < D + 1; i++) { int a = queue[head].x; if (map[a][i] == 1 && map[i][a] == 1) { if (color[a] == color[i]) {flag=false;return;} if(color[i]==0){ Node n2=new Node(); n2.x=i; queue[tail]=n2; tail++; if(color[a]==1){color[i]=2;} if(color[a]==2){color[i]=1;} } } } head++; } }
}
//
2 1 2 1
4 3 1 2 2 3 3 4
5 5 1 2 2 3 3 4 4 5 5 1
6 9 1 4 1 5 1 6 2 4 2 5 2 6 3 4 3 5 3 6
4 3 1 2 2 3 4 3
4 4 1 2 1 3 1 4 2 3
11 10 1 2 1 3 3 4 4 5 5 10 10 11 9 8 9 4 8 6 6 4
//
#1 1 1 #2 2 1 3 #3 -1 #4 3 1 2 3 #5 2 1 3 #6 -1 #7 4 1 4 8 10
