// 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"


  template < typename Graph >
    bool examine_edges(Graph & g)
  {

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

	get_eValidColors(g);

	for(color_iter=ColorList.begin(); color_iter != ColorList.end(); ++color_iter) {
	for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
		if( g[*ei].eWeight == "Heavy" ) continue;
		if( g[source(*ei,g)].vColor != g[target(*ei,g)].vColor ) continue;
		Conflicted = true;
			if( *color_iter == g[target(*ei,g)].vColor ) continue;
			if( g[*ei].eValidColors.find(*color_iter) == g[*ei].eValidColors.end() ) continue;
			g[*ei].ePColors.insert(make_pair(*color_iter,1)); 
			if( has_chainA(*ei, *color_iter, g) ) return true;
			Colored = true;
		}
	}


	if( !Conflicted ) { result = 0; return false; }
	if( !Colored ) { result = 1; return false; }

	return dotted(g);

  }

  template < typename Graph >
    bool dotted(Graph & g)
  {

    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++;
		for(color_iter=ColorList.begin(); color_iter != ColorList.end(); ++color_iter) {
			for(tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
			ColorPSet & Pin_color_set = g[*ei].ePColors;
				if( Pin_color_set.find(make_pair(*color_iter,i)) == Pin_color_set.end() ) continue;
				for(colorr_iter=ColorList.begin(); colorr_iter != ColorList.end(); ++colorr_iter) {
					for (tie(out_iter, out_end) = out_edges(target(*ei,g), g); out_iter != out_end; ++out_iter) {
						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;

						Pout_color_set.insert(make_pair(*colorr_iter,i+1));
						inserted = true;
						if( has_chain(i+1, *ei, *out_iter, *colorr_iter, g) ) return true;
					
					}
				}
			}
		}

	} while ( inserted );

	result = 2; 

	return false;

  }

  template < typename Edge, typename Graph >
    bool has_chainA(Edge out, Color color, 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" && g[target(*out_iter,g)].vColor == color ) return false;
	}

	g[out].eArrow = aColour_map[color];
	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)
  {

    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;
	do_chain(out, g);

	return true;

  }


  template < typename Edge, typename Graph >
    bool get_chain(int len, Edge out, Graph & g)
  {

    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;
		}
	}

	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)
  {

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

	if( g[source(in,g)].vNewColor != "nil" ) { return false; }

        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)
  {

	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; 
  }


  graph_t g;

  int main()
  {

	read_graphml(cin, g, dpp);

	while( examine_edges(g) );
			
	return result;

  }