#include "helpers.cpp"

#include<cstdio>
#include<vector>

#include <boost/config.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/astar_search.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/property_map/transform_value_property_map.hpp>

using namespace std;
using namespace boost;

typedef adjacency_list<listS, vecS, directedS, Vertex, Edge> Graph;
typedef graph_traits<Graph>::vertex_descriptor vertex_t;
typedef graph_traits<Graph>::edge_descriptor edge_t;
typedef graph_traits<Graph>::vertices_size_type Size;

Graph G;
unsigned N;
vector<Size> d;

class AStarHeuristic : public astar_heuristic<Graph, int> {
  public:
    int operator()( vertex_t v ) const {
        return G[v].h;
    }
};

struct FoundGoal {};

template <class Vertex>
class astar_vertex_visitor : public default_astar_visitor {
  public:
    astar_vertex_visitor(int* _count) { count=_count; }
    template <class Graph>
    void examine_vertex(Vertex u, Graph& g) {
        (*count)++;
        if (g[u].winning) {
            throw FoundGoal();
        }
    }
  private:
    int* count;
};

int main(int argc, char **argv) {
    string filename = argv[1];
    N = read(G, filename);

    vertex_t starting = get_starting(G);

    AStarHeuristic aStarHeuristic;
    d.resize(N);
    
    auto wmap = make_transform_value_property_map([](Edge& e) { return 1; }, get(edge_bundle, G));
    int count = 0;
    auto a_visitor = astar_vertex_visitor<vertex_t>(&count);

    try {
        astar_search_tree(
            G, starting,
            aStarHeuristic,
            distance_map(make_iterator_property_map(d.begin(), get(vertex_index, G))).
            weight_map(wmap).
            visitor(a_visitor));
    } catch(FoundGoal fg) {
        printf("%d\n", count);
        return 0;
    }
    printf("-1\n");
    return 0;

}
