#include "helpers.cpp"

#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/graph/iteration_macros.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/archive/binary_oarchive.hpp>
#include <boost/graph/adj_list_serialize.hpp> 
#include <boost/archive/text_iarchive.hpp>
#include <boost/graph/reverse_graph.hpp>
#include <boost/graph/copy.hpp>
#include <boost/graph/transpose_graph.hpp>

using namespace std;
using namespace boost;

typedef adjacency_list<listS, vecS, bidirectionalS, Vertex, Edge> BiGraph;
typedef reverse_graph<adjacency_list<listS, vecS, bidirectionalS, Vertex, Edge>> RGraph;
typedef graph_traits<BiGraph>::vertex_descriptor vertex_t;
typedef graph_traits<BiGraph>::vertex_iterator vertex_iter;
typedef graph_traits<BiGraph>::vertices_size_type Size;

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

vertex_t get_starting() {
    N++;
    vertex_t starting = add_vertex(G);
    G[starting].id = -1;
    std::pair<vertex_iter, vertex_iter> vp;
    for (vp = vertices(G); vp.first != vp.second; ++vp.first) {
        if (G[*vp.first].winning) {
            add_edge(*vp.first, starting, G);
        }
    }
    return starting;
}

void do_bfs(const RGraph& rG, vertex_t starting) {
    d.resize(N, 0);
    breadth_first_search(
            rG, starting, 
            visitor(
                make_bfs_visitor(record_distances(&d[0], on_tree_edge()))
                ));
}

int get_viable_states_count(const RGraph& rG) {
    std::pair<vertex_iter, vertex_iter> vp;
    int cnt = 0;
    for (vp = vertices(rG); vp.first != vp.second; ++vp.first) {
        if (d[*vp.first] > 0) {
            cnt++;
        }
    }
    return cnt;
}

int main(int argc , char* argv[]) {
    if (argc < 2) {
        return 0;
    }
    {
        string filename = argv[1];
        N = read(G, filename);
    }

    vertex_t starting = get_starting();

    RGraph r = make_reverse_graph(G);

    do_bfs(r, starting);

    printf("%d\n", get_viable_states_count(r));

    return 0;
}
