public class main {

	static Vertex verts[];
	static String brokenPath = ""; // this is used to record when a path breaks

	public static String getColorName(int b) {
		if (b==1)
			return "red";
		else
			return "blue";
	}

	public static boolean DFS(int src, boolean b) {
		// Assign a color to the source index
		if (verts[src] == null) {
			verts[src] = new Vertex();
		}
		Vertex vert = verts[src];
		vert.setColor(b);
		// caching color
		int col = vert.getColor();

		// update path with this vertex
		//path = path + src + "("+ getColorName(col)+ "), ";
		LinkedList<Integer> LL = vert.getList();
		for (int i : LL){
			// color 0 means undiscovered
			int col2 = verts[i].getColor();
			if (col2 == 0) {
				if (!DFS(i,!b)) {
					brokenPath = (i+1) + "(" + getColorName(verts[i].getColor()) + "), " + brokenPath;
					return false;
				}
			}
			// we found an invalid cycle, return here and provide appropriate broken string
			else if(col2 > 0 && col == col2) {
				brokenPath = "=> " + (i+1) + "(" + getColorName(col2) + "), ";
				return false;
			}
		}

		return true;
	}

	public static void main(String[] args) {
		if (args.length > 0 && args[0] != null) {
			try {
				FileReader r = new FileReader(args[0]);
				LineNumberReader lnr = new LineNumberReader(r);

				// by convention the # of vertices is included as the first entry

				try {
					int size = Integer.parseInt(lnr.readLine());
					verts = new Vertex[size];
					while(lnr.ready()) {
						String split[] = lnr.readLine().split(" ");
						//adds the vertex in
						int index1 = Integer.parseInt(split[0])-1;
						int index2 = Integer.parseInt(split[1])-1;// has to be corrected since arrays are zero'd
						// since edges are undirected, add them to each vertex, since traversal can happen either way
						if (verts[index1] == null)
							verts[index1] = new Vertex();
						if (verts[index2] == null)
							verts[index2] = new Vertex();
						verts[index2].add(index1);
						verts[index1].add(index2);
					}
					try {
						r.close();
						lnr.close();
					} catch (IOException e) {
						e.printStackTrace();
					}
					// Write output file
					try {
						FileOutputStream db = new FileOutputStream(args[1]);
						PrintWriter out = new PrintWriter(db);
						String start = "";
						boolean twoColorable = true;
						// loop through and find verticies that aren't discovered
						for (int s = 0; s<verts.length; s++) {
							if (verts[s] == null || verts[s].getColor() == 0) {
								start = (s+1) + "(red), ";
								if (!DFS(s, true)) {
									twoColorable = false;
									break;
								}
								else {
									start = "";
								}
							}
						}

						System.out.println(twoColorable);
						// write our output file according to the result
						out.println("Two colorable : " + twoColorable);
						if (twoColorable) {
							for (int i = 0; i<verts.length; i++) {
								if (verts[i] != null && verts[i].getColor() == 1) {
									out.println((i+1) + " = red");
								}
								else {
									out.println((i+1) + " = blue");
								}
							}
						}
						else {
							out.println(start + brokenPath);
						}
						out.flush();
						out.close();
					}
					catch(Exception e) {e.printStackTrace();}// errorr-ed

				// God... Could java get anymore messy?

				} catch (NumberFormatException e1) {
					e1.printStackTrace();
				} catch (IOException e1) {
					e1.printStackTrace();
				}
			} catch (FileNotFoundException e) {
				e.printStackTrace();
			}
		}
		else
			System.out.println("arguments <inputfile> <outputfile>");
	}

}