#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#include <map>
#include <queue>

using namespace std;

#define POSITIVE_INFINITY (1<<30)
#define NEGATIVE_INFINITY (-1*(1<<30))

class Graf{
public:
    struct edge{
        int from;
        int to;
        int cost;
    };
    Graf(int nrNodes, int nrEdges, bool isOriented, vector<vector<int>> &adjacencyList);
    Graf(int nrNodes, int nrEdges, bool isOriented, vector<vector<int>> &adjacencyList, bool isCostGraph, vector<edge> &edges);
    void test();
    vector<int> bfs(int start);
    int dfs();
    vector<vector<int>> biconnectedComponents();
    vector<int> topSort();
    vector<int> strongConnectedComponents();
    vector<int> eulerianCircuit();
    vector<int> dijkstra(int start);
    int getCost(int from, int to);
    vector<int> bellmanFord(int start);
    int darb();

private:
    //date membre
    int m_nrNodes;
    int m_nrEdges;
    bool m_isOriented;
    bool m_isCostGraph;
    vector<vector<int>> m_adjacencyList;
    vector<edge> m_edges;

    //functii ajutatoare
    void dfsRec(int start, vector<bool> &visited);
    void biconnectedComponentsDFS(int u, vector<int> &disc, vector<int> &low, vector<edge> &st, vector<int> &parent, vector<vector<int>> &result);
    int dfsTop(int idx, int crtNode, vector<bool> &visited, vector<int> &result);
    void dfsStrConComp(int i, vector<int> &ids, vector<int> &low, vector<bool> &isOnStack, vector<int> &stack, int &idx);
    int min(int a, int b);
    void euler(int node, vector<int> &result, vector<vector<int>> &adjencyList);
    pair<int, int> bfsDarb(int start);
};

Graf::Graf(int nrNodes, int nrEdges, bool isOriented, vector<vector<int>> &adjacencyList) {
    m_nrNodes = nrNodes;
    m_nrEdges = nrEdges;
    m_isOriented = isOriented;
    m_isCostGraph = false;
    edge crtEdge;
    m_adjacencyList.resize(nrNodes + 1);
    for(int i = 1; i <= nrNodes; i++){
        for(int j = 0; j < adjacencyList[i].size(); j++){
            m_adjacencyList[i].push_back(adjacencyList[i][j]);
            if(!isOriented){
                m_adjacencyList[adjacencyList[i][j]].push_back(i);
            }
            crtEdge.from = i;
            crtEdge.to = adjacencyList[i][j];
            crtEdge.cost = 1;
            m_edges.push_back(crtEdge);
        }
    }
}

void Graf::test(){
    cout << m_nrNodes << " " << m_nrEdges << '\n';
    for(int i = 1; i <= m_nrNodes; i++){
        cout<<i<<": ";
        for(int j : m_adjacencyList[i]){
            cout<<j<<", ";
        }
        cout<<'\n';
    }
}

Graf::Graf(int nrNodes, int nrEdges, bool isOriented, vector<vector<int>> &adjacencyList, bool isCostGraph, vector<edge> &edges) {
    m_nrNodes = nrNodes;
    m_nrEdges = nrEdges;
    m_isOriented = isOriented;
    m_isCostGraph = isCostGraph;
    m_adjacencyList.resize(nrNodes + 1);
    for(int i = 1; i <= nrNodes; i++){
        for(int j = 0; j < adjacencyList[i].size(); j++){
            m_adjacencyList[i].push_back(adjacencyList[i][j]);
            if(!isOriented){
                m_adjacencyList[adjacencyList[i][j]].push_back(i);
            }
        }
    }
    for(int i = 0; i < nrEdges; i++){
        edge crtEdge{edges[i].from, edges[i].to, edges[i].cost};
        m_edges.push_back(crtEdge);
    }
}

vector<int> Graf::bfs(int start) {
    vector<int> result;

    vector<bool> visited;
    for(int i=1; i<=m_nrNodes+1; i++){
        visited.push_back(false);
    }
    deque<int> dq;
    vector<int> prev;
    for(int i=1; i<=m_nrNodes+1; i++){
        prev.push_back(0);
    }

    dq.push_back(start);
    visited[start] = true;

    while(!dq.empty()){
        int crt = dq.front();
        dq.pop_front();
        for(int i : m_adjacencyList[crt]){
            if(!visited[i]){
                dq.push_back(i);
                visited[i] = true;
                prev[i] = crt;
            }
        }
    }

    for(int f = 1; f <= m_nrNodes; f++){
        int steps = 0;
        int lastVisited;
        for(int i = f; i != 0; i = prev[i]){
            steps++;
            lastVisited = i;
        }

        if(lastVisited != start) { result.push_back(-1); }
        else { result.push_back(steps - 1); }
    }

    return result;
}

int Graf::dfs() {//ar trebui mai degraba sa tina de dfs infoarena cred, dar vad eu
    vector<bool> visited;
    for(int i = 0; i <= m_nrNodes; i++){
        visited.push_back(false);
    }

    int nrConexComponents = 0;

    for(int i = 1; i <= m_nrNodes; i++){
        if(!visited[i]){
            nrConexComponents++;
            dfsRec(i, visited);
        }
    }

    return nrConexComponents;
}

void Graf::dfsRec(int start, vector<bool> &visited) {
    visited[start] = true;
    for(auto i : m_adjacencyList[start]){
        if(!visited[i]){
            dfsRec(i, visited);
        }
    }
}

vector<vector<int>> Graf::biconnectedComponents() {
    vector<int> disc, low, parent;
    vector<edge> st;

    // Initialize disc and low, and parent arrays
    for (int i = 0; i <= m_nrNodes; i++) {
        disc.push_back(-1);
        low.push_back(-1);
        parent.push_back(-1);
    }

    vector<vector<int>> result;

    for (int i = 1; i <= m_nrNodes; i++) {
        if (disc[i] == -1)
            biconnectedComponentsDFS(i, disc, low, st, parent, result);

        vector<int> component;

        int j = 0;
        // If stack is not empty, pop all edges from stack
        while (!st.empty()) {
            j = 1;
            bool isFrom = false, isTo = false;
            for(int node : component){
                if(node == st.back().to){
                    isTo = true;
                }
                if(node == st.back().from){
                    isFrom = true;
                }
            }
            if(!isFrom && !isTo){
                component.push_back(st.back().to);
            }
            else if(isFrom && !isTo){
                component.push_back(st.back().to);
            }
            else if(!isFrom && isTo){
                component.push_back(st.back().from);
            }
            st.pop_back();
        }
        if (j == 1) {
            result.push_back(component);
        }
    }

    return result;
}

void Graf::biconnectedComponentsDFS(int u, vector<int> &disc, vector<int> &low, vector<edge> &st, vector<int> &parent, vector<vector<int>> &result) {
    static int time = 0;

    // Initialize discovery time and low value
    disc[u] = low[u] = ++time;
    int children = 0;

    // Go through all vertices adjacent to this
    for (auto v : m_adjacencyList[u]) {

        // If v is not visited yet, then recur for it
        if (disc[v] == -1) {
            children++;
            parent[v] = u;
            // store the edge in stack
            edge crtEdge{u, v, 0};
            st.push_back(crtEdge);
            biconnectedComponentsDFS(v, disc, low, st, parent, result);

            // Check if the subtree rooted with 'v' has a
            // connection to one of the ancestors of 'u'
            if(low[u] > low[v]) low[u] = low[v];

            vector<int> component;
            // If u is an articulation point,
            // pop all edges from stack till u -- v
            if ((disc[u] == 1 && children > 1) || (disc[u] > 1 && low[v] >= disc[u])) {
                while (st.back().from != u || st.back().to != v) {
                    bool isFrom = false, isTo = false;
                    for(int node : component){
                        if(node == st.back().to){
                            isTo = true;
                        }
                        if(node == st.back().from){
                            isFrom = true;
                        }
                    }
                    if(!isFrom && !isTo){
                        component.push_back(st.back().to);
                    }
                    else if(isFrom && !isTo){
                        component.push_back(st.back().to);
                    }
                    else if(!isFrom && isTo){
                        component.push_back(st.back().from);
                    }
                    st.pop_back();
                }
                bool isFrom = false, isTo = false;
                for(int node : component){
                    if(node == st.back().to){
                        isTo = true;
                    }
                    if(node == st.back().from){
                        isFrom = true;
                    }
                }
                if(!isFrom && !isTo){
                    component.push_back(st.back().to);
                }
                else if(isFrom && !isTo){
                    component.push_back(st.back().to);
                }
                else if(!isFrom && isTo){
                    component.push_back(st.back().from);
                }
                st.pop_back();
                result.push_back(component);
            }
        }

        else if (v != parent[u]) {
            if(low[u] > low[v]) low[u] = low[v];

            if (disc[v] < disc[u]) {
                edge crtEdge{u, v, 0};
                st.push_back(crtEdge);
            }
        }
    }
}

vector<int> Graf::topSort() {
    vector<bool> visited;
    for(int i = 0; i <= m_nrNodes; i++){
        visited.push_back(false);
    }
    vector<int> result;
    result.resize(m_nrNodes);
    int idx = m_nrNodes - 1;

    for(int i = 1; i <= m_nrNodes; i++){
        if(!visited[i]){
            idx = dfsTop(idx, i, visited, result);
        }
    }

    return result;
}

int Graf::dfsTop(int idx, int crtNode, vector<bool> &visited, vector<int> &result) {
    visited[crtNode] = true;

    for(int i : m_adjacencyList[crtNode]){
        if(!visited[i]){
            idx = dfsTop(idx, i, visited, result);
        }
    }

    result[idx] = crtNode;
    return idx - 1;
}

vector<int> Graf::strongConnectedComponents() {
    int idx = 0;
    vector<int> ids, low;
    vector<bool> isOnStack;
    vector<int> stack;
    low.resize(m_nrNodes + 1);
    isOnStack.resize(m_nrNodes + 1);
    for(int i = 0; i <= m_nrNodes; i++){
        ids.push_back(-1);
    }

    for(int i = 1; i <= m_nrNodes; i++){
        if(ids[i] == -1){
            dfsStrConComp(i, ids, low, isOnStack, stack, idx);
        }
    }

    return low;
}

void Graf::dfsStrConComp(int i, vector<int> &ids, vector<int> &low, vector<bool> &isOnStack, vector<int> &stack, int &idx) {
    stack.push_back(i);
    isOnStack[i] = true;
    ids[i] = low[i] = ++idx;

    for(auto to : m_adjacencyList[i]){
        if(ids[to] == -1) dfsStrConComp(to, ids, low, isOnStack, stack, idx);
        if(isOnStack[to]) low[i] = min(low[i], low[to]);
    }

    if(ids[i] == low[i]){
//        while(!stack.empty()){
//            if(stack.back() == i) break;
//            isOnStack[stack.back()] = false;
//            low[stack.back()] = ids[i];
//            stack.pop_back();
//        }
        for(auto node = stack.back(); !stack.empty(); stack.pop_back()){
            isOnStack[node] = false;
            low[node] = ids[i];
            if(node == i) break;
        }
    }
}

int Graf::min(int a, int b) {
    if(a < b) return a;
    return b;
}

vector<int> Graf::eulerianCircuit() {
    vector<int> result;

    for (int i = 1; i <= m_nrNodes; i++) {
        if (m_adjacencyList[i].size() % 2) {
            result.push_back(-1);
            return result;
        }
    }//daca gasim vreun nod cu grad impar atunci nu avem ciclu Euler

    vector<vector<int>> adjacencyListCopy = m_adjacencyList;
    euler(1, result, adjacencyListCopy);

    return result;
}

void Graf::euler(int node, vector<int> &result, vector<vector<int>> &adjencyList) {
    while(!adjencyList[node].empty()){
        int next = adjencyList[node].back();
        adjencyList[node].pop_back();
        for(auto i = adjencyList[next].begin(); i != adjencyList[next].end(); i++){
            if(*i == node){
                adjencyList[next].erase(i);
                break;
            }
        }
        euler(next, result, adjencyList);
    }
    result.push_back(node);
}

vector<int> Graf::dijkstra(int start) {
    vector<int> dist;
    vector<bool> visited;
    for(int i = 0; i <= m_nrNodes; i++){
        visited.push_back(false);
        dist.push_back(1 << 30);
    }
    dist[start] = 0;
    priority_queue<pair<int, int>> pq; // pq(dist, node)
    pq.push(make_pair(0, start));
    while(!pq.empty()){
        pair<int, int> pair = pq.top(); //make_pair(minValue, index)
        cout<<pair.first<<" "<<pair.second<<'\n';
        visited[pair.second] = true;
        if(dist[pair.second] < pair.first) continue;
        for(int next : m_adjacencyList[pair.second]){
            if(visited[next]) continue;
            int newDist = dist[pair.second] + getCost(pair.second, next);
            if(newDist < dist[next]){
                dist[next] = newDist;
                pq.push(make_pair(newDist, next));
                //cout<<newDist<<" "<<next<<'\n';
            }
        }
        pq.pop();
    }

    return dist;
}

int Graf::getCost(int from, int to) {
    if(from == to) return 0;
    for(int i = 0; i < m_nrEdges; i++){
        if(m_edges[i].from == from && m_edges[i].to == to){
            return m_edges[i].cost;
        }
    }

    return -1;
}

vector<int> Graf::bellmanFord(int start) {
    vector<int> dist;
    for(int i = 0; i <= m_nrNodes + 1; i++){
        dist.push_back(POSITIVE_INFINITY);
    }
    dist[start] = 0;

    for(int i = 0; i < m_nrNodes - 1; i++){
        for(edge edge : m_edges){
            if(dist[edge.from] + edge.cost < dist[edge.to]){
                dist[edge.to] = dist[edge.from] + edge.cost;
            }
        }
    }
    //run again to find negative cycles
    for(int i = 0; i < m_nrNodes - 1; i++){
        for(edge edge : m_edges){
            if(dist[edge.from] + edge.cost < dist[edge.to]){
                dist[edge.to] = NEGATIVE_INFINITY;
                dist[0] = NEGATIVE_INFINITY;
            }
        }
    }

    return dist;
}

pair<int, int> Graf::bfsDarb(int start) {//returns (lastVisited, val)

    vector<bool> visited;
    for(int i=1; i<=m_nrNodes+1; i++){
        visited.push_back(false);
    }
    deque<int> dq;
    vector<int> prev;
    for(int i=1; i<=m_nrNodes+1; i++){
        prev.push_back(0);
    }

    dq.push_back(start);
    visited[start] = true;

    int lastVisited;

    while(!dq.empty()){
        int crt = dq.front();
        dq.pop_front();
        for(int i : m_adjacencyList[crt]){
            if(!visited[i]){
                dq.push_back(i);
                visited[i] = true;
                prev[i] = crt;

                lastVisited = i;
            }
        }
    }
    int steps = 0;

    for(int i = lastVisited; i != 0; i = prev[i]){
        steps++;
    }

    return make_pair(lastVisited, steps);
}

int Graf::darb() {
    pair<int, int> lastVisitedAndPathSize = bfsDarb(1);

    int darb = bfsDarb(lastVisitedAndPathSize.first).second;
    return darb;
}

void bfsInfoArena(){
    ifstream fin("bfs.in");
    ofstream fout("bfs.out");

    int n, m, x, from, to;
    vector<vector<int>> la;

    fin>>n>>m>>x;

    la.resize(n+1);
    for(int i = 0; i < m; i++){
        fin>>from>>to;
        la[from].push_back(to);
    }
    Graf graf = Graf(n, m, true, la);
    vector<int> res = graf.bfs(x);
    for(int i : res){
        fout<<i<<" ";
    }
}

void dfsInfoArena(){
    ifstream fin("dfs.in");
    ofstream fout("dfs.out");

    int n, m, from, to;
    vector<vector<int>> la;

    fin>>n>>m;

    la.resize(n+1);
    for(int i = 0; i < m; i++){
        fin>>from>>to;
        la[from].push_back(to);
    }
    Graf graf = Graf(n, m, false, la);
    fout<<graf.dfs();
}

void biconexInfoArena(){
    ifstream fin("biconex.in");
    ofstream fout("biconex.out");

    int n, m, from, to;
    vector<vector<int>> la;

    fin>>n>>m;

    la.resize(n+1);
    for(int i = 0; i < m; i++){
        fin>>from>>to;
        la[from].push_back(to);
    }
    Graf graf = Graf(n, m, false, la);
    vector<vector<int>> componenteBiconexe = graf.biconnectedComponents();
    fout<<componenteBiconexe.size()<<'\n';
    for(auto i: componenteBiconexe){
        for(auto j : i){
            fout<<j<<" ";
        }
        fout<<'\n';
    }
}

void sortaretInfoArena(){
    ifstream fin("sortaret.in");
    ofstream fout("sortaret.out");

    int n, m, from, to;
    vector<vector<int>> la;

    fin>>n>>m;

    la.resize(n+1);
    for(int i = 0; i < m; i++){
        fin>>from>>to;
        la[from].push_back(to);
    }
    Graf graf = Graf(n, m, true, la);
    vector<int> sortare = graf.topSort();
    for(auto i: sortare){
        fout<<i<<" ";
    }
}

void ctcInfoArena(){
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");

    int n, m, from, to;
    vector<vector<int>> la;

    fin>>n>>m;

    la.resize(n+1);
    for(int i = 0; i < m; i++){
        fin>>from>>to;
        la[from].push_back(to);
    }
    Graf graf = Graf(n, m, true, la);
    vector<int> rezultat = graf.strongConnectedComponents();
//    for(auto i: rezultat){
//        cout<<i<<" ";
//    }
    map<int, vector<int>> componente;
    for(int i = 1; i <= n; i++){
        componente[rezultat[i]].push_back(i);
    }
    fout<<componente.size()<<'\n';
    for(auto comp : componente){
        for(auto nod : comp.second){
            fout<<nod<<" ";
        }
        fout<<'\n';
    }
}

void dijkstraInfoArena(){
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");

    int n, m, from, to, cost;
    vector<vector<int>> la;
    vector<Graf::edge> edges;

    fin>>n>>m;

    la.resize(n+1);
    for(int i = 0; i < m; i++){
        fin>>from>>to>>cost;
        la[from].push_back(to);
        Graf::edge crtEdge{from, to, cost};
        edges.push_back(crtEdge);
    }
    Graf graf = Graf(n, m, true, la, true, edges);
    vector<int> rezultat = graf.dijkstra(1);
    for(int i = 2; i <= n; i++){
        fout<<rezultat[i]<<" ";
    }
    //graf.test();
}

void cicluEulerianInfoArena(){
    ifstream fin("ciclueuler.in");
    ofstream fout("ciclueuler.out");

    int n, m, from, to;
    vector<vector<int>> la;

    fin>>n>>m;

    la.resize(n+1);
    for(int i = 0; i < m; i++){
        fin>>from>>to;
        la[from].push_back(to);
    }
    Graf graf = Graf(n, m, false, la);
    vector<int> rezultat = graf.eulerianCircuit();
    for(auto i: rezultat){
        fout<<i<<" ";
    }
}

void bellmanFordInfoArena(){
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");

    int n, m, from, to, cost;
    vector<vector<int>> la;
    vector<Graf::edge> edges;

    fin>>n>>m;

    la.resize(n+1);
    for(int i = 0; i < m; i++){
        fin>>from>>to>>cost;
        la[from].push_back(to);
        Graf::edge crtEdge{from, to, cost};
        edges.push_back(crtEdge);
    }
    Graf graf = Graf(n, m, true, la, true, edges);
    vector<int> rezultat = graf.bellmanFord(1);
    if(rezultat[0] == NEGATIVE_INFINITY) fout<<"Ciclu negativ!";
    else{
        for(int i = 2; i <= n; i++){
            fout<<rezultat[i]<<" ";
        }
    }
}

void darbInfoArena(){
    ifstream fin("darb.in");
    ofstream fout("darb.out");

    int n, from, to;
    vector<vector<int>> la;

    fin>>n;

    la.resize(n+1);
    for(int i = 0; i < n-1; i++){
        fin>>from>>to;
        la[from].push_back(to);
    }
    Graf graf = Graf(n, n-1, false, la);
    int res = graf.darb();

    fout<<res;
}

int main() {

    darbInfoArena();

    return 0;
}