#include <algorithm>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>

namespace gtc
{

/*****************************************************************************
 * class _base_graph                                                         *
 *****************************************************************************/



template <typename K, typename W, typename T>
class _base_graph
{
protected:

    _base_graph()
    {
    }

    _base_graph(size_t n);

    _base_graph(size_t n, const K& k);

    template <typename F>
    _base_graph(size_t n, F f);

public:
    void add_node(const K& k);

    void add_node(const K& k, const T& t);

    std::size_t order()
    {
        return nod.size();
    }

    size_t size()
    {
        return edg.size();
    }


    T& operator[] (const K& k);

    class iterator
    {
        friend class _base_graph<K, W, T>;
    public:

        iterator& operator++()
        {
            ++it;
            return *this;
        }

        iterator operator++(int)
        {
            iterator i = (*this);
            ++it;
            return i;
        }

        iterator& operator--()
        {
            --it;
            return *this;
        }

        iterator operator--(int)
        {
            iterator i = (*this);
            --it;
            return i;
        }

        std::pair<const K, T>& operator*()
        {
            return *it;
        }

        std::pair<const K, T>* operator-> ()
        {
            return &(*it);
        }

        bool operator==(const iterator& i)
        {
            return it == i.it;
        }

        bool operator!=(const iterator& i)
        {
            return it != i.it;
        }

    private:
        typename std::map<K, T>::iterator begin, end;
        typename std::map<K, T>::iterator it;
    };

    virtual iterator begin();

    virtual iterator end();

    virtual iterator find(const K& k);

    class edge
    {
    public:

        edge(const K& k1, const K& k2, const W& w = 0) :
        ky1(k1), ky2(k2), wt(w)
        {
        }

        bool operator==(const edge& e) const
        {
            return key1() == e.key1() && key2() == e.key2();
        }

        bool operator!=(const edge& e) const
        {
            return key1() != e.key1() || key2() != e.key2();
        }

        const K& key1() const
        {
            return ky1;
        }

        const K& key2() const
        {
            return ky2;
        }


        const K& key(const K& k);

        K& weight()
        {
            return wt;
        }

    private:
        K ky1;
        K ky2;
        W wt;
    };

    virtual bool is_edge(const K& k1, const K& k2) = 0;

    class edge_iterator
    {
        friend class _base_graph<K, W, T>;
    public:
        edge_iterator& operator++();
        edge_iterator operator++(int);
        edge_iterator& operator--();
        edge_iterator operator--(int);

        edge& operator*()
        {
            return *it;
        }

        edge* operator-> ()
        {
            return &(*it);
        }

        bool operator==(const edge_iterator& i)
        {
            return it == i.it;
        }

        bool operator!=(const edge_iterator& i)
        {
            return it != i.it;
        }

    private:
        typename std::list<edge>::iterator begin, end;
        typename std::list<edge>::iterator it;

        K key;
    };

    edge_iterator begin(const K& k);

    edge_iterator end(const K& k);

    template <typename F>
    F BFS(const K& k, F f);

    template <typename F>
    F DFS(const K& k, F f);

protected:
    std::map<K, T> nod;
    std::list<edge> edg;
};

template <typename K, typename W, typename T>
_base_graph<K, W, T>::_base_graph(size_t n)
{
    K key(1);

    for (size_t i = 0; i < n; i++)
        nod[key++] = T();
}

template <typename K, typename W, typename T>
_base_graph<K, W, T>::_base_graph(size_t n, const K& k)
{
    K key(k);

    for (size_t i = 0; i < n; i++)
        nod[key++] = T();
}

template <typename K, typename W, typename T>
template <typename F>
_base_graph<K, W, T>::_base_graph(size_t n, F f)
{
    for (size_t i = 0; i < n; i++)
        nod[f()] = T();
}

template <typename K, typename W, typename T>
void _base_graph<K, W, T>::add_node(const K& k)
{
    if (nod.find(k) != nod.end())
        throw std::string("_base_graph::add_node - node already exists");
    nod[k] = T();
}

template <typename K, typename W, typename T>
void _base_graph<K, W, T>::add_node(const K& k, const T& t)
{
    if (nod.find(k) != nod.end())
        throw std::string("_base_graph::add_node - node already exists");
    nod[k] = t;
}

template <typename K, typename W, typename T>
typename _base_graph<K, W, T>::iterator _base_graph<K, W, T>::begin()
{
    iterator i;
    i.begin = nod.begin();
    i.end = nod.end();

    i.it = i.begin;

    return i;
}

template <typename K, typename W, typename T>
typename _base_graph<K, W, T>::edge_iterator _base_graph<K, W, T>::begin(const K& k)
{
    edge_iterator i;
    i.begin = edg.begin();
    i.end = edg.end();
    i.key = k;

    i.it = i.begin;
    while (i.it != i.end && i.it->key1() != i.key && i.it->key2() != i.key)
    {
        i.it++;
    }

    return i;
}

template <typename K, typename W, typename T>
typename _base_graph<K, W, T>::iterator _base_graph<K, W, T>::end()
{
    iterator i;
    i.begin = nod.begin();
    i.end = nod.end();

    i.it = i.end;

    return i;
}

template <typename K, typename W, typename T>
typename _base_graph<K, W, T>::edge_iterator _base_graph<K, W, T>::end(const K& k)
{
    edge_iterator i;
    i.begin = edg.begin();
    i.end = edg.end();
    i.key = k;

    i.it = i.end;

    return i;
}

template <typename K, typename W, typename T>
typename _base_graph<K, W, T>::iterator _base_graph<K, W, T>::find(const K& k)
{
    iterator i;
    i.begin = nod.begin();
    i.end = nod.end();
    i.it = nod.find(k);

    return i;
}

template <typename K, typename W, typename T>
template <typename F>
F _base_graph<K, W, T>::BFS(const K& k, F f)
{
    K cur;
    std::queue<K> q;
    std::set<K> v;

    q.push(k);
    v.insert(k);

    while (!q.empty())
    {

        cur = q.front();
        q.pop();
        f(cur);

        for (iterator i = begin(); i != end(); i++)
            if (is_edge(cur, i->first))
                if (v.find(i->first) == v.end())
                {
                    q.push(i->first);
                    v.insert(i->first);
                }
    }

    return f;
}

template <typename K, typename W, typename T>
template <typename F>
F _base_graph<K, W, T>::DFS(const K& k, F f)
{
    K cur = k;
    std::set<K> v;
    std::stack<K> s;

    do
    {
        if (v.find(cur) == v.end())
        {
            f(cur);
            s.push(cur);
            v.insert(cur);
        }
        iterator i = begin();
        while (i != end() && v.find(i->first) != v.end())
            i++;
        if (i != end())
            cur = i->first;
        else
        {
            s.pop();
            if (!s.empty())
                cur = s.top();
        }
    }
    while (!s.empty());

    return f;
}

template <typename K, typename W, typename T>
T& _base_graph<K, W, T>::operator[] (const K& k)
{
    if (nod.find(k) == nod.end())
        throw std::string("_base_graph::operator[] - node does not exist");
    return nod[k];
}

template <typename K, typename W, typename T>
const K& _base_graph<K, W, T>::edge::key(const K& k)
{
    if (k != key1() && k != key2())
        throw std::string("graph::edge::key - key supplied is invalid");

    return k == key1() ? key2() : key1();
}

template <typename K, typename W, typename T>
typename _base_graph<K, W, T>::edge_iterator& _base_graph<K, W, T>::edge_iterator::operator++()
{
    ++it;
    while (it != end && it->key1() != key && it->key2() != key)
        ++it;

    return *this;
}

template <typename K, typename W, typename T>
typename _base_graph<K, W, T>::edge_iterator _base_graph<K, W, T>::edge_iterator::operator++(int)
{
    edge_iterator tmp = *this;

    ++it;
    while (it != end && it->key1() != key && it->key2() != key)
        ++it;

    return tmp;
}

template <typename K, typename W, typename T>
typename _base_graph<K, W, T>::edge_iterator& _base_graph<K, W, T>::edge_iterator::operator--()
{
    --it;
    while (it != begin && it->key1() != key && it->key2() != key)
        --it;
    if (it == begin)
        while (it != end && it->key1() != key && it->key2() != key)
            ++it;

    return *this;
}

template <typename K, typename W, typename T>
typename _base_graph<K, W, T>::edge_iterator _base_graph<K, W, T>::edge_iterator::operator--(int)
{
    edge_iterator tmp = *this;

    --it;
    while (it != begin && it->key1() != key && it->key2() != key)
        --it;
    if (it == begin)
        while (it != end && it->key1() != key && it->key2() != key)
            ++it;

    return tmp;
}

/*****************************************************************************
 * class graph                                                               *
 *****************************************************************************/


template <typename K, typename T = void*>
        class graph : public _base_graph<K, void*, T>
{
public:

    graph() : _base_graph<K, void*, T>()
    {
    }

    graph(size_t n) : _base_graph<K, void*, T>(n)
    {
    }

    graph(size_t n, const K& k) : _base_graph<K, void*, T>(n, k)
    {
    }

    template <typename F>
    graph(size_t n, F f) : _base_graph<K, void*, T>(n, f)
    {
    }

    void add_edge(const K& k1, const K& k2);

    bool is_edge(const K& k1, const K& k2);

    void remove_edge(const K& k1, const K& k2);
};

template <typename K, typename T>
void graph<K, T>::add_edge(const K& k1, const K& k2)
{
    if (nod.find(k1) == nod.end() || nod.find(k2) == nod.end())
        throw std::string("add_edge: Node does not exist");

    // Store lower key value in first key of edge
    if (k1 < k2)
        edg.push_back(edge(k1, k2));
    else
        edg.push_back(edge(k2, k1));
}

template <typename K, typename T>
bool graph<K, T>::is_edge(const K& k1, const K& k2)
{
    if (nod.find(k1) == nod.end() || nod.find(k2) == nod.end())
        throw std::string("is_edge: Node does not exist");

    if (k1 < k2)
        return std::find(edg.begin(), edg.end(), edge(k1, k2)) != edg.end();
    return std::find(edg.begin(), edg.end(), edge(k2, k1)) != edg.end();
}

template <typename K, typename T>
void graph<K, T>::remove_edge(const K& k1, const K& k2)
{
    if (nod.find(k1) == nod.end() || nod.find(k2) == nod.end())
        throw std::string("add_edge: Node does not exist");

    if (k1 < k2)
        edg.remove(edge(k1, k2));
    else
        edg.remove(edge(k2, k1));
}

/*****************************************************************************
 * class wgraph                                                              *
 *****************************************************************************/


template <typename K, typename W, typename T = void*>
        class wgraph : public _base_graph<K, W, T>
{
public:

    wgraph() : _base_graph<K, W, T>()
    {
    }

    wgraph(size_t n) : _base_graph<K, W, T>(n)
    {
    }

    wgraph(size_t n, const K& k) : _base_graph<K, W, T>(n, k)
    {
    }

    template <typename F>
    wgraph(size_t n, F f) : _base_graph<K, W, T>(n, f)
    {
    }

    void add_edge(const K& k1, const K& k2, const W& w);

    bool is_edge(const K& k1, const K& k2);

    void remove_edge(const K& k1, const K& k2);

    W& weight(const K& k1, const K& k2);
};

template <typename K, typename W, typename T>
void wgraph<K, W, T>::add_edge(const K& k1, const K& k2, const W& w)
{
    if (nod.find(k1) == nod.end() || nod.find(k2) == nod.end())
        throw std::string("add_edge: Node does not exist");

    // Store lower key value in first key of edge
    if (k1 < k2)
        edg.push_back(edge(k1, k2, w));
    else
        edg.push_back(edge(k2, k1, w));
}

template <typename K, typename W, typename T>
bool wgraph<K, W, T>::is_edge(const K& k1, const K& k2)
{
    if (nod.find(k1) == nod.end() || nod.find(k2) == nod.end())
        throw std::string("is_edge: Node does not exist");

    if (k1 < k2)
        return std::find(edg.begin(), edg.end(), edge(k1, k2)) != edg.end();
    return std::find(edg.begin(), edg.end(), edge(k2, k1)) != edg.end();
}

template <typename K, typename W, typename T>
void wgraph<K, W, T>::remove_edge(const K& k1, const K& k2)
{
    if (nod.find(k1) == nod.end() || nod.find(k2) == nod.end())
        throw std::string("add_edge: Node does not exist");

    if (k1 < k2)
        edg.remove(edge(k1, k2));
    else
        edg.remove(edge(k2, k1));
}

template <typename K, typename W, typename T>
W& wgraph<K, W, T>::weight(const K& k1, const K& k2)
{
    if (nod.find(k1) == nod.end() || nod.find(k2) == nod.end())
        throw std::string("weight: Node does not exist");
    if (!is_edge(k1, k2))
        throw std::string("weight: Edge does not exist");

    if (k1 < k2)
        return std::find(edg.begin(), edg.end(), edge(k1, k2))->weight();
    return std::find(edg.begin(), edg.end(), edge(k2, k1))->weight();
}

/*****************************************************************************
 * class digraph                                                             *
 *****************************************************************************/


template <typename K, typename T = void*>
        class digraph : public _base_graph<K, void*, T>
{
public:

    digraph() : _base_graph<K, void*, T>()
    {
    }

    digraph(size_t n) : _base_graph<K, void*, T>(n)
    {
    }

    digraph(size_t n, const K& k) : _base_graph<K, void*, T>(n, k)
    {
    }

    template <typename F>
    digraph(size_t n, F f) : _base_graph<K, void*, T>(n, f)
    {
    }

    void add_edge(const K& k1, const K& k2);

    bool is_edge(const K& k1, const K& k2);

    void remove_edge(const K& k1, const K& k2);
};

template <typename K, typename T>
void digraph<K, T>::add_edge(const K& k1, const K& k2)
{
    if (nod.find(k1) == nod.end() || nod.find(k2) == nod.end())
        throw std::string("add_edge: Node does not exist");

    edg.push_back(edge(k1, k2));
}

template <typename K, typename T>
bool digraph<K, T>::is_edge(const K& k1, const K& k2)
{
    if (nod.find(k1) == nod.end() || nod.find(k2) == nod.end())
        throw std::string("is_edge: Node does not exist");

    return std::find(edg.begin(), edg.end(), edge(k1, k2)) != edg.end();
}

template <typename K, typename T>
void digraph<K, T>::remove_edge(const K& k1, const K& k2)
{
    if (nod.find(k1) == nod.end() || nod.find(k2) == nod.end())
        throw std::string("add_edge: Node does not exist");

    edg.remove(edge(k1, k2));
}

/*****************************************************************************
 * class wdigraph                                                            *
 *****************************************************************************/


template <typename K, typename W, typename T = void*>
        class wdigraph : public _base_graph<K, W, T>
{
public:

    wdigraph() : _base_graph<K, W, T>()
    {
    }

    wdigraph(size_t n) : _base_graph<K, W, T>(n)
    {
    }

    wdigraph(size_t n, const K& k) : _base_graph<K, W, T>(n, k)
    {
    }

    template <typename F>
    wdigraph(size_t n, F f) : _base_graph<K, W, T>(n, f)
    {
    }

    void add_edge(const K& k1, const K& k2, const W& w);

    bool is_edge(const K& k1, const K& k2);

    void remove_edge(const K& k1, const K& k2);

    W& weight(const K& k1, const K& k2);
};

template <typename K, typename W, typename T>
void wdigraph<K, W, T>::add_edge(const K& k1, const K& k2, const W& w)
{
    if (nod.find(k1) == nod.end() || nod.find(k2) == nod.end())
        throw std::string("add_edge: Node does not exist");

    edg.push_back(edge(k1, k2, w));
}

template <typename K, typename W, typename T>
bool wdigraph<K, W, T>::is_edge(const K& k1, const K& k2)
{
    if (nod.find(k1) == nod.end() || nod.find(k2) == nod.end())
        throw std::string("is_edge: Node does not exist");

    return std::find(edg.begin(), edg.end(), edge(k1, k2)) != edg.end();
}

template <typename K, typename W, typename T>
void wdigraph<K, W, T>::remove_edge(const K& k1, const K& k2)
{
    if (nod.find(k1) == nod.end() || nod.find(k2) == nod.end())
        throw std::string("add_edge: Node does not exist");

    edg.remove(edge(k1, k2));
}

template <typename K, typename W, typename T>
W& wdigraph<K, W, T>::weight(const K& k1, const K& k2)
{
    if (nod.find(k1) == nod.end() || nod.find(k2) == nod.end())
        throw std::string("weight: Node does not exist");
    if (!is_edge(k1, k2))
        throw std::string("weight: Edge does not exist");

    return std::find(edg.begin(), edg.end(), edge(k1, k2))->weight();
}

} // namespace gtc

int main()
{
    return 0;
}