#include <iostream>
#include <fstream>
#include <vector>
#include <limits.h>
#include <queue>

using namespace std;

class Graph{

    //DATE MEMBRE
private:

    int m_graph_nodes;
    //numar de noduri

    vector<vector<int>> m_graph_adjacency_list;
    //lista de adiacenta

    vector<vector<pair<int,int>>> m_graph_adjacency_list_with_costs;
    //lista de adiacenta pentru graf cu costuri

    vector<vector<int>> m_costs_matrix;
    //matricea de costuri pentru grafuri ponderate

    vector<vector<int>> m_capacities;

public:
    //METODELE CLASEI

    //CITIRILE

    void read_graph_with_costs_as_costs_matrix(char *file);
    //citire graf orientat ponderat cu matricea costurilor

    void read_transport_routes(char *file);
    //citire retea de trasnport

    void read_unoriented_tree_without_costs_as_adjacency_list(char *file);
    //primeste calea catre fisierul text si citeste un graf neorientat fara costuri ca lista de adiacenta

    void read_oriented_graph_without_costs_as_adjacency_list(char *file);
    //primeste calea catre fisierul text si citeste un graf orientat fara costuri

    //ALGORITMI FUNDAMENTALI

    vector<int> BFS(int nod);
    //BFS

    vector<vector<int>> roy_floyd();
    //algoritmul roy floyd -> returneaza matricea drumurilor din matricea costurilor asociata grafului apelant

    int edmonds_karp();
    //algoritmul edmonds karp -> returneaza fluxul maxim

    //HELPERE

    void BFS_diametru(int nod,int& diametru, int& last);

    void print_path_matrix(vector<vector<int>> path_matrix, char *file);
    //functia care afiseaza in fisier matricea drumurilor

//METODE UTILE IN METODELE PUBLICE
private:
    int minimum_length_BFS(vector<vector<int>> &flows, vector<int> &tata, vector<int> &viz, vector<int>& cd);
    //pentru edmonds karp
};

//METODELE PUBLICE

//  CITIRI

void Graph::read_graph_with_costs_as_costs_matrix(char *file) {
    ifstream f(file);
    vector<int> aux;

    f >> this->m_graph_nodes;

    m_costs_matrix.push_back(aux);

    for(int i = 1; i <= this->m_graph_nodes; i++){
        vector<int> linie;
        linie.push_back(0);

        for(int j = 1; j <= this->m_graph_nodes; j++){
            int val;
            f >> val;
            linie.push_back(val);
        }

        m_costs_matrix.push_back(linie);
    }
}

void Graph::read_transport_routes(char *file) {
    ifstream f(file);
    int number_edges;
    vector<int> aux;

    f >> this->m_graph_nodes;

    this->m_graph_adjacency_list.assign(this->m_graph_nodes + 1, aux);

    aux.assign(this->m_graph_nodes + 1, 0);
    this->m_capacities.assign(this->m_graph_nodes + 1, aux);

    f >> number_edges;

    for(int i = 0; i < number_edges; i++){
        int x, y, z;

        f >> x >> y >> z;

        this->m_capacities[x][y] = this->m_capacities[x][y] + z;

        this->m_graph_adjacency_list[x].push_back(y);
        this->m_graph_adjacency_list[y].push_back(x);
    }
}

void Graph::read_unoriented_tree_without_costs_as_adjacency_list(char *file) {
    ifstream f(file);
    vector<int> aux;

    f >> this->m_graph_nodes;

    this->m_graph_adjacency_list.assign(this->m_graph_nodes + 1, aux);

    for(int i = 0; i < this->m_graph_nodes; i++){
        int x, y;
        f >> x >> y;

        this->m_graph_adjacency_list[x].push_back(y);
        this->m_graph_adjacency_list[y].push_back(x);
    }
}

//ALGORITMI FUNDAMENTALI

vector<int> Graph::BFS(int nod){
    //initializam vectorul de distante minime

    vector<int> distante;
    distante.assign(this->m_graph_nodes + 1, 0);

    int curent;
    //in coada vom pune nodurile pe massura ce le parcurgem
    queue<int> coada;

    //initial toate nodurile sunt nevizitate, asaa ca initializam viz[orice nod] = 0
    vector<int> viz;
    viz.assign(this->m_graph_nodes + 1, 0);

    //adaugam nodul sursa in coada si il marcam ca si vizitat
    coada.push(nod);
    viz[nod] = 1;

    //actualizam vectorul de distante pentru nodul curent cu distanta pana la el, adica 1
    distante[nod] = distante[nod] + 1;

    //facem BFS-ul
    while(!coada.empty()){

        curent = coada.front();

        //parcurgem vecinii nodului curent si pe fiecare vecin nevizitat il adaugam in coada, ii actualizam distanta pana la el si il marcam ca si vizitat

        for(int i=0; i < this->m_graph_adjacency_list[curent].size(); i++){

            if(viz[this->m_graph_adjacency_list[curent][i]] == 0){
                coada.push(this->m_graph_adjacency_list[curent][i]);

                distante[coada.back()] = distante[curent]+1;

                viz[this->m_graph_adjacency_list[curent][i]] = 1;
            }
        }

        //am terminat cu nodul curent, il scoatem din coada
        coada.pop();
    }
    return distante;
}

vector<vector<int>> Graph::roy_floyd() {
    vector<vector<int>> path_matrix;
    vector<int> aux;

    aux.assign(this->m_graph_nodes + 1, 0);
    path_matrix.assign(this->m_graph_nodes + 1, aux);

    for(int i = 1; i <= this->m_graph_nodes; i++){

        for(int j = 1; j <= this->m_graph_nodes; j++){

            path_matrix[i][j] = this->m_costs_matrix[i][j];
        }
    }

    for(int k = 1; k <= this->m_graph_nodes; k++){

        for(int i = 1; i <= this->m_graph_nodes; i++){

            for(int j = 1; j <= this->m_graph_nodes; j++){

                if(i != j && path_matrix[i][k] != 0 && path_matrix[k][j] != 0){

                    if(path_matrix[i][j] > path_matrix[i][k] + path_matrix[k][j]){

                        path_matrix[i][j] = path_matrix[i][k] + path_matrix[k][j];

                    }else if (path_matrix[i][j] == 0){

                        path_matrix[i][j] = path_matrix[i][k] + path_matrix[k][j];
                    }
                }
            }
        }
    }

    return path_matrix;
}

int Graph::edmonds_karp() {
    int max_flow = 0;
    vector<vector<int>> flows;
    vector<int> tata;
    vector<int> viz;
    vector<int> cd;

    tata.assign(this->m_graph_nodes + 1, 0);
    flows.assign(this->m_graph_nodes + 1, tata);
    viz.assign(this->m_graph_nodes + 1, 0);
    cd.assign(this->m_graph_nodes + 1, 0);

    while(this->minimum_length_BFS(flows, tata, viz, cd) != 0){

        for(int i = 0; i < this->m_graph_adjacency_list[this->m_graph_nodes].size(); i++){

            int neighbor;

            neighbor = this->m_graph_adjacency_list[this->m_graph_nodes][i];

            if(flows[neighbor][this->m_graph_nodes] != this->m_capacities[neighbor][this->m_graph_nodes] && viz[neighbor] == 0){

                tata[this->m_graph_nodes] = neighbor;

                int min_flow = INT_MAX;
                for(int j = this->m_graph_nodes; j != 1; j = tata[j]){
                    if(min_flow > this->m_capacities[tata[j]][j] - flows[tata[j]][j]){
                        min_flow = this->m_capacities[tata[j]][j] - flows[tata[j]][j];
                    }
                }

                if(min_flow != 0){

                    for(int j = this->m_graph_nodes; j != 1; j = tata[j]){

                        flows[tata[j]][j] = flows[tata[j]][j] + min_flow;
                        flows[j][tata[j]] = flows[j][tata[j]] - min_flow;
                    }

                    max_flow = max_flow + min_flow;
                }
            }
        }
    }

    return max_flow;
}

//HELPERE

void Graph::BFS_diametru(int nod,int& diametru, int& last){
    //initializam vectorul de distante minime

    vector<int> distante;
    distante.assign(this->m_graph_nodes + 1, 0);

    int curent;
    //in coada vom pune nodurile pe massura ce le parcurgem
    queue<int> coada;

    //initial toate nodurile sunt nevizitate, asaa ca initializam viz[orice nod] = 0
    vector<int> viz;
    viz.assign(this->m_graph_nodes + 1, 0);

    //adaugam nodul sursa in coada si il marcam ca si vizitat
    coada.push(nod);
    viz[nod] = 1;

    //actualizam vectorul de distante pentru nodul curent cu distanta pana la el, adica 1
    distante[nod] = distante[nod] + 1;

    //facem BFS-ul
    while(!coada.empty()){

        curent = coada.front();

        //parcurgem vecinii nodului curent si pe fiecare vecin nevizitat il adaugam in coada, ii actualizam distanta pana la el si il marcam ca si vizitat

        for(int i=0; i < this->m_graph_adjacency_list[curent].size(); i++){

            if(viz[this->m_graph_adjacency_list[curent][i]] == 0){
                coada.push(this->m_graph_adjacency_list[curent][i]);

                distante[coada.back()] = distante[curent]+1;

                viz[this->m_graph_adjacency_list[curent][i]] = 1;

                diametru = distante[this->m_graph_adjacency_list[curent][i]];
                last = this->m_graph_adjacency_list[curent][i];
            }
        }

        //am terminat cu nodul curent, il scoatem din coada
        coada.pop();
    }
}

void Graph::print_path_matrix(vector<vector<int>> path_matrix, char *file) {

    ofstream out(file);

    for(int i = 1; i <= this->m_graph_nodes; i++){

        for(int j = 1; j <= this->m_graph_nodes; j++){
            out<<path_matrix[i][j]<<" ";
        }

        out<<"\n";
    }
}

//FUNCTII PRIVATE UTILE
int Graph::minimum_length_BFS(vector<vector<int>> &flows, vector<int> &tata, vector<int> &viz, vector<int>& cd) {

    viz.assign(this->m_graph_nodes + 1, 0);

    cd[0] = cd[1] = 1;
    viz[1] = 1;

    for(int i = 1; i <= cd[0]; i++){
        int node;

        node = cd[i];
        if(node != this->m_graph_nodes){
            for(int j = 0; j < this->m_graph_adjacency_list.size(); j++){
                int vecin;
                vecin = this->m_graph_adjacency_list[node][j];
                if(this->m_capacities[node][vecin] != flows[node][vecin] && viz[vecin] == 0){
                    viz[vecin] = 1;
                    cd[++cd[0]] = vecin;
                    tata[vecin] = node;
                }
            }
        }
    }

    return viz[this->m_graph_nodes];
}

int main() {

    //FLOYD WARSALL INFOARENA

    /*Graph g;
    g.read_graph_with_costs_as_costs_matrix("../royfloyd.in");
{1}
    vector<vector<int>> path_matrix;
    path_matrix = g.roy_floyd();
    g.print_path_matrix(path_matrix,"../royfloyd.out");*/

    //MAXFLOW INFOARENA

    /*ofstream out("../maxflow.out");
    Graph g;
    int max_flow;
    g.read_transport_routes("../ maxflow.in");
    max_flow = g.edmonds_karp();
    out<<max_flow;*/

    //DIAMETRU ARBORE INFOARENA
    Graph g;
    ofstream out("../darb.out");

    g.read_unoriented_tree_without_costs_as_adjacency_list("../darb.in");

    int diametru = 0, last = 0;

    g.BFS_diametru(1,diametru,last);
    g.BFS_diametru(last,diametru,last);

    out<<diametru;
    return 0;
}