#include <vector>

 #include <lemon/smart_graph.h>

 #include <lemon/bin_heap.h>

 #include <lemon/graph_reader.h>

 #include <lemon/graph_to_eps.h>

 using namespace std;

 using namespace lemon;

 int main() {

   typedef UndirSmartGraph Graph;

   typedef Graph::Node Node;

   typedef Graph::NodeIt NodeIt;

   typedef Graph::UndirEdge UndirEdge;

   typedef Graph::IncEdgeIt IncEdgeIt;

   Graph graph;

   UndirGraphReader<Graph> reader(std::cin, graph);

   Graph::NodeMap<xy<double> > coords(graph);

   reader.readNodeMap("coords", coords);

   reader.run();

   Graph::NodeMap<int> color(graph, -2);

   Graph::NodeMap<int> heapMap(graph, -1);

   BinHeap<Node, int, Graph::NodeMap<int> > heap(heapMap);

   for (NodeIt it(graph); it != INVALID; ++it) {

     heap.push(it, countOutEdges(graph, it));

   }

   vector<Node> order;

   while (!heap.empty()) {

     Node node = heap.top();

     heap.pop();

     color[node] = -1;

     order.push_back(node);

     for (IncEdgeIt it(graph, node); it != INVALID; ++it) {

       Node target = graph.runningNode(it); 

       if (color[target] == -2) {

 	heap.decrease(target, heap[target] - 1);

       }

     }

   }

   for (int i = order.size() - 1; i >= 0; --i) {

     set<int> forbidden;

     for (IncEdgeIt it(graph, order[i]); it != INVALID; ++it) {

       Node target = graph.runningNode(it); 

       if (color[target] != -1) {

 	forbidden.insert(color[target]);

       }

     }

     int current = 0;

     while (forbidden.find(current) != forbidden.end()) ++current;

     color[order[i]] = current;

   }

   ColorSet colorSet;

   graphToEps(graph, "six_coloring.eps").

     title("Six Colored Graph").copyright("(C) 2005 LEMON Project").

     coords(coords).nodeColors(composeMap(colorSet, color)).

     scaleToA4().run();

   return 0;

 }