#include <iostream>
#include <cstring>
#include <fstream>
#include <sstream>
#include <vector>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/boyer_myrvold_planar_test.hpp>
#include <boost/graph/planar_face_traversal.hpp>

typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_index_t, int> > Graph;

typedef boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
typedef boost::graph_traits<Graph>::edge_descriptor edge_descriptor;

typedef std::vector< std::vector< boost::graph_traits<Graph>::edge_descriptor > >  planar_embedding_storage_t;
typedef boost::iterator_property_map< planar_embedding_storage_t::iterator, boost::property_map<Graph, boost::vertex_index_t>::type > planar_embedding_t;

struct output_visitor : public boost::planar_face_traversal_visitor
    {
        void begin_face() { std::cout << "New face: "; }
        template <typename Vertex> void next_vertex(Vertex v) { std::cout << v << " "; } 
        void finish_face() { std::cout << std::endl; }
    };


int main(int argc, char* argv[])
{
  int n, m;
  std::ifstream file;
  std::string line;
  std::istringstream ss;

  if (argc < 2) {
    std::cerr << argv[0] << ": missing input file name.\n";
    return 1;
  }

  file.open(argv[1]);
  if (!file) {
    std::cerr << argv[0] << ": cannot open file `" << argv[1] << "\'" << std::endl;
    return 1;
  }

  char j;
  bool found;
  output_visitor vis;
  edge_descriptor e;
  vertex_descriptor u, v;

  while ( std::getline(file, line) ) {
    ss.str(line);
    ss >> n;
    Graph g(n);

    // Create an instance of the storage and the property map
    planar_embedding_storage_t planar_embedding_storage(boost::num_vertices(g));
    planar_embedding_t planar_embedding(planar_embedding_storage.begin(),
                                    boost::get(boost::vertex_index, g) );

    for (int i = 0; i < n; ++i) {
      u = boost::vertex(i, g);
      while (ss >> j) {
        if (j == ' ') continue;
        if (j == ',') break;
        boost::add_edge(i, j - 'a', g);
        v = boost::vertex(j - 'a', g);
        boost::tie(e, found) = boost::edge(u, v, g);
        planar_embedding[u].push_back(e);
      }
    }

    if ( !boost::boyer_myrvold_planarity_test(g) ) {
      std::cerr << "warning: " << line
                << " should have been recognized as planar." << std::endl;
      return 1;
    }

    boost::planar_face_traversal(g, &planar_embedding[0], vis);

    ss.clear();
    g.clear();
    planar_embedding_storage.clear();
    exit(0);
  }

  file.close();
  return 0;
}