#include<cstdio>
#include<vector>

#include <boost/config.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/archive/text_iarchive.hpp>
#include <boost/graph/adj_list_serialize.hpp> 
#include <boost/graph/graph_traits.hpp>

using namespace std;

class Vertex {
public:
    int id;
    bool starting, winning;
    int h, min_pushes;
    friend class boost::serialization::access;
    template<class Archive>
    void serialize(Archive & ar, const unsigned int version) {
        ar & id;
        ar & starting;
        ar & winning;
        ar & h;
        ar & min_pushes;
    }
};

class Edge {
public:
    bool pushed;
    friend class boost::serialization::access;
    template<class Archive>
    void serialize(Archive & ar, const unsigned int version) {
        ar & pushed;
    }
};

class SccVertex {
public:
    int id;
    bool starting, winning;
    int size;
    friend class boost::serialization::access;
    template<class Archive>
    void serialize(Archive & ar, const unsigned int version) {
        ar & id;
        ar & starting;
        ar & winning;
        ar & size;
    }
};

namespace boost {

template<typename T>
unsigned read(T& G, const string& filename) {
    std::ifstream dot(filename);
    boost::archive::text_iarchive ia(dot);
    ia >> G;
    return num_vertices(G);
}

// Debug function.
template<typename T>
void print_g(T G) {
    dynamic_properties dpDual; 
    dpDual.property("node_id", get(vertex_index, G)); 
    dpDual.property("id", get(&Vertex::id, G)); 
    dpDual.property("starting", get(&Vertex::starting, G)); 
    dpDual.property("winning", get(&Vertex::winning, G));   
    dpDual.property("h", get(&Vertex::h, G));   
    dpDual.property("min_pushes", get(&Vertex::min_pushes, G));   
    write_graphviz_dp(std::cout, G, dpDual); 

    for (auto vp = edges(G); vp.first != vp.second; ++vp.first) {
        int x = G[target(*vp.first, G)].min_pushes - G[source(*vp.first, G)].min_pushes > 0 ? 1 : 0;
        printf("%d %d %d\n", G[source(*vp.first, G)].id, G[target(*vp.first, G)].id, x);
    }
    printf("\n");
}

// Get the only starting vertex.
template<typename T>
typename graph_traits<T>::vertex_descriptor get_starting(const T& G) {
    for (auto vp = vertices(G); vp.first != vp.second; ++vp.first) {
        if (G[*vp.first].starting) {
            return *vp.first;
        }
    }
    return 0;
}

// Loop over all vertices, filtering only winning ang getting the shortest solution.
template<typename T>
typename graph_traits<T>::vertices_size_type get_shortest_path(
        const T& G,
        const vector<typename graph_traits<T>::vertices_size_type>& d
) {
    typename graph_traits<T>::vertices_size_type shortest = -1;
    bool found = false;
    for (auto vp = vertices(G); vp.first != vp.second; ++vp.first) {
        if (G[*vp.first].winning) {
            typename graph_traits<T>::vertices_size_type dis = d[*vp.first];
            if (!found || shortest > dis) {
                found = true;
                shortest = dis;
            }
        }
    }
    return shortest;
}

}
