// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)


#include "Declarations.cpp"
#include "Utilities.cpp"


    // Each edge e of the graph contains a set of pairs of type pair< Color, int >, it's ePColors.
    // Let e's ePColors contain for example (Red, 5). This is intended to indicate that e is 
    // potentially the 5_th edge of a free alternating chain where e is colored Red.
    // We find a succession of free alternating chains.

  template < typename Graph >
    bool examine_edges(Graph & g)
  { // Mark light conflicted edges first. One of these edges will be the first edge of any free alternating chain we find.

    typename graph_traits<Graph>::edge_iterator ei, ei_end;
    bool Colored = false, Conflicted = false;
	
    Color_List::iterator color_iter;

	// Determine valid edge colors.
	get_eValidColors(g);

	// For each color *color_iter in the list (Red, Green, Blue, Yellow)
	for(color_iter=ColorList.begin(); color_iter != ColorList.end(); ++color_iter) {
	// For each edge *ei
	for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
		// If *ei is light and *ei is conflicted (ie. has the same color vertices at both ends)
		if( g[*ei].eWeight == "Heavy" ) continue;
		if( g[source(*ei,g)].vColor != g[target(*ei,g)].vColor ) continue;
		Conflicted = true;
			// and *color_iter is not the same color as the vertex on the end of the edge, 
			if( *color_iter == g[target(*ei,g)].vColor ) continue;
			// and *color_iter is a valid color for *ei
			if( g[*ei].eValidColors.find(*color_iter) == g[*ei].eValidColors.end() ) continue;
			// then insert the pair (*color_iter, 1) in the ePColors of *out_iter. 
			g[*ei].ePColors.insert(make_pair(*color_iter,1)); 
			
			// Check to see if this yields a free alternating chain of length 1.
			// If so apply the chain to the graph 
			// (ie. make heavy (darken) this edge and change the vertex color at the end of the chain in accordance with the 
			// coloring found in the function "has_chainA", so that this edge is no longer conflicted).
			// Then return, and look for the next free alternating chain. 
			if( has_chainA(*ei, *color_iter, g) ) return true;
			Colored = true;
		}
	}


	if( !Conflicted ) { result = 0; return false; } // If !Conflicted the graph is properly four colored, algorithm succeeds, we are done.
	if( !Colored ) { result = 1; return false; } // If !Colored, graph is conflicted but not colorable (no new pair can be put in any edge's ePColors) - algorithm fails.

	// If no free alternating chain of length one has been found we must look for a free alternating chain of lenght two ( then 3,4, ... ) by going to function dotted.
	return dotted(g);

  }

  template < typename Graph >
    bool dotted(Graph & g)
  { // Mark Heavy edges.
    // We look for a free alternating chain of length two (then three, four ...).

    typename graph_traits<Graph>::edge_iterator ei, ei_end;
    typename graph_traits<Graph>::out_edge_iterator out_iter, out_end;

    Color_List::iterator color_iter, colorr_iter;

    bool inserted;
    int i = 0;

	do {
		inserted = false;
		i++; // i will become 1 for the first iteration through the loop, when we are looking for a free alternating chain of length 2.
		// We assume that i is 1 in the comments that follow.
		// For each color *color_iter in the list (Red, Green, Blue, Yellow)
		for(color_iter=ColorList.begin(); color_iter != ColorList.end(); ++color_iter) {
			// For each edge *ei
			for(tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
				// Let Pin_color_set be *ei's ePColors.
				ColorPSet & Pin_color_set = g[*ei].ePColors;
				// If we are trying to find a free alternating chain of length two, then we need to find a pair, (*color_iter, 1), in Pin_color_set ( notice the 1).
				// If Pin_color_set does not contain such a pair continue.
				if( Pin_color_set.find(make_pair(*color_iter,i)) == Pin_color_set.end() ) continue;
				// Now considering all possible colors 
				for(colorr_iter=ColorList.begin(); colorr_iter != ColorList.end(); ++colorr_iter) {
					// look at all edges outgoing from the target of *ei. 
					for (tie(out_iter, out_end) = out_edges(target(*ei,g), g); out_iter != out_end; ++out_iter) {
						// If the edges *ei and *out_iter satisfy certain conditions,
						if( target(*out_iter,g) == source(*ei,g) ) continue;
						if( g[*out_iter].eWeight == "Light" ) continue;
						if( *color_iter != g[target(*out_iter,g)].vColor ) continue;
						ColorPSet & Pout_color_set = g[*out_iter].ePColors;
						ColorSet & eValid_out_color_set = g[*out_iter].eValidColors;
						if( *colorr_iter == g[target(*out_iter,g)].vColor ) continue;
						if( eValid_out_color_set.find(*colorr_iter) == eValid_out_color_set.end() ) continue;
						if( PColorsFind(*out_iter, *colorr_iter, g) ) continue;

						// then insert the pair (*colorr_iter, 2) in the ePColors of *out_iter. 
						Pout_color_set.insert(make_pair(*colorr_iter,i+1));
						inserted = true; // Keep track that a new pair was inserted.

						// Check to see if this yields a free alternating chain.
						// If so apply the chain to the graph, return true, and look for the next free alternating chain.
						if( has_chain(i+1, *ei, *out_iter, *colorr_iter, g) ) return true;
					
					}
				}
			}
		}

	// If inserted = true and no free alternating chain of length two (three, four ...)  has been found we must look for a 
	// free alternating chain of length three (four, five ...) by going through this while loop again.
	} while ( inserted );

	// If we get here then the function "has_chain(i+1, *ei, *out_iter, *colorr_iter, g)" above has not returned true, and "inserted" has not been set to true because no new 
	// pair can be put in any edge's ePColors. The algorithm has failed to find a four coloring. Set result to 2 (Failure) and return false (end program).

	result = 2; 

	return false;

  }

  template < typename Edge, typename Graph >
    bool has_chainA(Edge out, Color color, Graph & g)
  { // Determine if a free alternating chain of length 1 has been found.

    typename graph_traits<Graph>::out_edge_iterator out_iter, out_end;

	for(tie(out_iter, out_end) = out_edges(target(out,g),g); out_iter != out_end; ++out_iter) {
		if( target(*out_iter,g) == source(out,g) ) continue;
		if( g[*out_iter].eWeight == "Heavy" && g[target(*out_iter,g)].vColor == color ) return false;
	}

	g[out].eArrow = aColour_map[color];
     	// If so apply the chain to the graph 
	if( do_chain(out, g) ) return true;

	return false;

  }


  template < typename Edge, typename Graph >
    bool has_chain(int len, Edge ei, Edge out, Color color, Graph & g)
  { // Determine if a free alternating chain of length greater than 1 has been found.
    // (This is basically a setup function for the recursive function get_chain(int len, Edge out, Graph & g).)

    typename graph_traits<Graph>::out_edge_iterator out_iter, out_end;

	for(tie(out_iter, out_end) = out_edges(target(out,g),g); out_iter != out_end; ++out_iter) {
		if( target(*out_iter,g) == source(out,g) ) continue;
		if( g[*out_iter].eWeight == "Heavy" && color == g[target(*out_iter,g)].vColor ) return false;
	}

	g[out].eArrow = aColour_map[color];
	g[target(out,g)].vNewColor = color;
	if( !get_chain(len, out, g) ) return false;
     	// If so apply the chain to the graph.
	do_chain(out, g);

	return true;

  }


  template < typename Edge, typename Graph >
    bool get_chain(int len, Edge out, Graph & g)
  { // Recursively call this function to get the free alternating chain.

    typename graph_traits<Graph>::in_edge_iterator in_iter, in_end;
    Color_List::iterator color_iter;


	if( g[out].eWeight == "Light" ) {
		g[out].ePredecessor = out;
		return true;
	}


        for (tie(in_iter, in_end) = in_edges(source(out,g), g); in_iter != in_end; ++in_iter) {
                if( source(*in_iter,g) == target(out,g) ) continue;
		if( g[*in_iter].eWeight != "Heavy" && g[source(*in_iter,g)].vColor != g[target(*in_iter,g)].vColor ) continue;
		ColorPSet & Pcolor_set = g[*in_iter].ePColors;
		for(color_iter=ColorList.begin(); color_iter != ColorList.end(); ++color_iter) {
			if( Pcolor_set.find(make_pair(*color_iter,len-1)) == Pcolor_set.end() ) continue;
			if( *color_iter == g[source(out,g)].vColor ) continue;
			if( *color_iter != g[target(out,g)].vColor ) continue;
			if( !valid(*in_iter, *color_iter, g) ) continue;

			g[out].ePredecessor = *in_iter;
			g[*in_iter].eArrow = aColour_map[*color_iter];
			g[target(*in_iter,g)].vNewColor = *color_iter;
			if( get_chain(len-1, *in_iter, g) ) return true; // recursive call
		}
	}

	g[out].ePredecessor = out;
	g[out].eArrow = "nil";
	g[target(out,g)].vNewColor = "nil";
	
        return false;

  }

  template < typename Edge, typename Graph >
    bool valid(Edge in, Color color, Graph & g)
  { // Determine if Edge "in" can have it's Color correctly set to "color" in the formation of a free alternating chain .
    // (This is NOT the same as eValidColors.)

    typename graph_traits<Graph>::in_edge_iterator in_iter, in_end;

	// in's source vertex must not yet (in the current attempt to get a free alternating chain) have been set to a color, so is still "nil".
	if( g[source(in,g)].vNewColor != "nil" ) { return false; }

	// No other heavy edge pointing to in's target vertex can have had it's source vertex colored "color".
        for (tie(in_iter, in_end) = in_edges(target(in,g), g); in_iter != in_end; ++in_iter) {
		if( source(*in_iter,g) == source(in,g) ) continue;
		if( g[*in_iter].eWeight == "Light" ) continue;
		if( color == g[source(*in_iter,g)].vNewColor ) { return false; }
	}


	return true;

  }


  template < typename Edge, typename Graph >
    bool do_chain(Edge in, Graph & g)
  { // Apply the chain to the graph.
    // Make the first edge heavy (dark), recolor al vertices along the chain except the first in accordance with the coloring found in the function "has_chain", or "has_chainA". 
    // The resulting graph will have one more heavy edge and be properly colored wrt. it's heavy edges. 

	g[target(in,g)].vColor = inverse_aColour_map[g[in].eArrow];

	if( g[in].eWeight == "Light" ) { 
		make_heavy(in, g); 
		initialize_arrows(g); 
		initialize_ePColors(g); 
		initialize_vNewColors(g);
		numChains++;
		return true; 
	}
	else do_chain(g[in].ePredecessor, g);

	return false; 
  }


  template < typename Graph >
    void fill_eValidColors(Graph & g)
  { // Insert all colors in each edges set of valid colors - eValidColors. Then erase invalid colors in get_eValidColors(Graph & g) below.

    typename graph_traits<Graph>::edge_iterator ei, ei_end;

	for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
		ColorSet & csr = g[*ei].eValidColors;
		for (Color_List::iterator color_iter = ColorList.begin(); color_iter != ColorList.end(); ++color_iter)
			csr.insert(*color_iter);
	}
			
 }




  template < typename Graph >
    void get_eValidColors(Graph & g)
  { // Erase invalid colors from each edges set of valid colors - eValidColors.

    typename graph_traits<Graph>::vertex_iterator vi, vi_end;
    typename graph_traits<Graph>::in_edge_iterator in_iter, in_end, in1_iter, in1_end, in2_iter, in2_end;

	fill_eValidColors(g);
        
	for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
		for (tie(in_iter, in_end) = in_edges(*vi, g); in_iter != in_end; ++in_iter) {
			// Consider the set of valid colors of in_iter, e_valid_colors.
			ColorSet & e_valid_colors = g[*in_iter].eValidColors;
				for (tie(in1_iter, in1_end) = in_edges(*vi, g); in1_iter != in1_end; ++in1_iter) {
					if( in1_iter == in_iter ) continue;
					if( g[*in1_iter].eWeight == "Light" ) continue;
					for (tie(in2_iter, in2_end) = in_edges(*vi, g); in2_iter != in2_end; ++in2_iter) {
						if( in2_iter == in_iter ) continue;
						if( g[*in2_iter].eWeight == "Light" ) continue;
						if( in2_iter == in1_iter ) continue;
						// If we arive at this point we have found two heavy edges incident with *vi 
						// other than in_iter, namely *in1_iter and *in2_iter.
						// If *in1_iter and *in2_iter have the same color at their other vertex ( not *vi )
						// then that color must be erased from the set of valid colors of in_iter ( e_valid_colors ).
						if( g[source(*in2_iter,g)].vColor == g[source(*in1_iter,g)].vColor ) 
							e_valid_colors.erase(g[source(*in1_iter,g)].vColor); 
					}
				}
		}
	}

 }




  graph_t g;

  int main()
  {

	read_graphml(cin, g, dpp);

	while( examine_edges(g) );
			
	return result; // Failure or Success

  }