#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <climits>
using namespace std;
ifstream f("darb.in");
ofstream o("darb.out");
class Graph
{
const int INF= INT_MAX;
void DFS(int node, vector<bool> &vis)
{
vis[node] = true;
for (auto i : adjList[node])
if (!vis[i])
DFS(i, vis);
}
void DFS1(int node, vector<bool> &vis, stack<int> &S)
{
vis[node] = true;
for (auto i : adjList[node])
if (!vis[i])
DFS1(i, vis, S);
S.push(node);
}
void DFS2(int node, vector<bool> &vis, vector<vector<int>> &scc, int it)
{
vis[node] = true;
scc[it].push_back(node);
for (auto i : adjList[node])
if (!vis[i])
DFS2(i, vis, scc, it);
}
void DFS_sortaret(int node, vector<bool> &vis, stack<int> &S)
{
vis[node] = true;
for (auto i : adjList[node])
if (!vis[i])
DFS_sortaret(i, vis, S);
S.push(node);
}
Graph TransposeGraph()
{
Graph Tg(size,false);
for (int i = 0; i < size; i++)
for (auto j : adjList[i])
Tg.adjList[j].push_back(i);
return Tg;
}
void dfs_base(int node, int k, bool visited[], int &diameter,int &fnode)
{
visited[node] = true;
k++;
for (auto i : adjList[node])
{
if (!visited[i])
{
if (k >= diameter)
{
diameter = k;
fnode = i;
}
dfs_base(i, k, visited, diameter,fnode);
}
}
}
void dfs_darb(int node, int &diameter,int &fnode)
{
bool *visited = new bool[size];
int k = 0;
for (int i = 0; i < size; i++)
visited[i] = false;
dfs_base(node, k + 1, visited, diameter,fnode);
}
bool hk_bfs(vector<int> &toRight, vector<int> &toLeft, vector<int> &dist)
{
queue<int> q;
for (int u = 1; u <= size; u++)
{
if (toRight[u] == 0)
{
dist[u] = 0;
q.push(u);
}
else
dist[u] = INF;
}
dist[0] = INF;
while (!q.empty())
{
int u = q.front();
q.pop();
if (dist[u] < dist[0])
{
for (auto i:adjList[u])
{
int v = i;
if (dist[toLeft[v]] == INF)
{
dist[toLeft[v]] = dist[u] + 1;
q.push(toLeft[v]);
}
}
}
}
return (dist[0] != INF);
}
bool hk_dfs(int u, vector<int> &toRight, vector<int> &toLeft, vector<int> &dist)
{
if (u != 0)
{
for (auto i : adjList[u])
{
int v = i;
if (dist[toLeft[v]] == dist[u] + 1)
{
if (hk_dfs(toLeft[v], toRight, toLeft, dist) == true)
{
toLeft[v] = u;
toRight[u] = v;
return true;
}
}
}
dist[u] = INF;
return false;
}
return true;
}
public:
vector<vector<int>> adjList;
vector<vector<pair<int, int>>> adjListW;
int size,size2;
Graph(int n,bool isWeighted)
{
size = n;
//true for weighted graph , false for unweighted graph
if(isWeighted)
adjListW.resize(size);
else
adjList.resize(size);
}
Graph(int n,int m,bool option)
{
size = n;
size2 = m;
//true for maximum bipartite matching , false for eulerian cycle
if(option)
adjList.resize(size+1);
else
adjList.resize(size);
}
void addEdgeD(int start, int end)
{
adjList[start].push_back(end);
}
void addEdgeU(int start, int end)
{
adjList[start].push_back(end);
adjList[end].push_back(start);
}
void addEdgeDW(int start, int end, int weight)
{
adjListW[start].push_back(make_pair(end, weight));
}
void addEdgeUW(int start, int end, int weight)
{
adjListW[start].push_back(make_pair(end, weight));
adjListW[end].push_back(make_pair(start, weight));
}
void addEdgeMultigraph(int start, int end, int i, vector<int> &source, vector<int> &destination)
{
adjList[start].push_back(i);
adjList[end].push_back(i);
source.push_back(start);
destination.push_back(end);
}
vector<int> BFS(int node) //BFS
{
vector<int> Cost;
queue<int> Q;
for (int i = 0; i < size; i++)
Cost.push_back(-1);
Cost[node] = 0;
Q.push(node);
while (!Q.empty())
{
node = Q.front();
Q.pop();
for (auto i : adjList[node])
if (Cost[i] == -1)
{
Cost[i] = Cost[node] + 1;
Q.push(i);
}
}
return Cost;
}
int Connected() //DFS
{
vector<bool> vis;
for (int i = 0; i < size; i++)
vis.push_back(false);
int k = 0;
for (int i = 0; i < size; i++)
if (!vis[i])
{
DFS(i, vis);
k++;
}
return k;
}
pair<int,vector<vector<int>>> SCC() //ctc
{
int it = 0;
vector<vector<int>> scc;
stack<int> S;
vector<bool> vis;
for (int i = 0; i < size; i++)
vis.push_back(false);
for (int i = 0; i < size; i++)
if (!vis[i])
DFS1(i, vis, S);
Graph Tg = TransposeGraph();
for (int i = 0; i < size; i++)
vis[i] = false;
while (!S.empty())
{
int node = S.top();
S.pop();
if (!vis[node])
{
scc.resize(it + 1);
Tg.DFS2(node, vis, scc, it);
it++;
}
}
/*for (int i = 0; i < scc.size(); i++)
for (int j = 0; j < scc[i].size(); j++)
scc[i][j]++;*/
return {it,scc};
/*o << it << endl;
for (int i = 0; i < scc.size(); i++)
{
for (int j = 0; j < scc[i].size(); j++)
o << scc[i][j] + 1 << " ";
o << endl;
}*/
}
vector<int> tS() //sortaret
{
vector<int> res;
stack<int> S;
vector<bool> vis;
for (int i = 0; i < size; i++)
vis.push_back(false);
for (int i = 0; i < size; i++)
if (!vis[i])
DFS_sortaret(i, vis, S);
while (!S.empty())
/*{
o << S.top() + 1 << " ";
S.pop();
}*/
{
res.push_back(S.top()+1);
S.pop();
}
return res;
}
vector<pair<int,int>> MST() //apm
{
vector<pair<int,int>> res;
int Tcost = 0, src = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
vector<int> parent(size, -1);
vector<int> cost(size, INF);
vector<bool> inMST(size, false);
pq.push(make_pair(0, src));
cost[src] = 0;
while (!pq.empty())
{
int u = pq.top().second;
pq.pop();
if (!inMST[u])
{
inMST[u] = true;
for (auto i : adjListW[u])
{
int v = i.first;
int weight = i.second;
if (!inMST[v] && cost[v] > weight)
{
cost[v] = weight;
pq.push(make_pair(cost[v], v));
parent[v] = u;
}
}
}
}
for (auto elem : cost)
Tcost += elem;
res.push_back(make_pair(Tcost,size-1));
for (int i = 1; i < size; i++)
res.push_back(make_pair(parent[i]+1,i+1));
return res;
}
vector<int> Dijkstra() //dijkstra
{
int src = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
vector<int> dist(size, INF);
pq.push(make_pair(0, src));
dist[src] = 0;
while (!pq.empty())
{
int u = pq.top().second;
pq.pop();
for (auto i : adjListW[u])
{
int v = i.first;
int weight = i.second;
if (dist[v] > dist[u] + weight)
{
dist[v] = dist[u] + weight;
pq.push(make_pair(dist[v], v));
}
}
}
for (int i = 1; i < size; i++)
if (dist[i] == INF)
dist[i]=0;
return dist;
}
vector<int> BellmanFord() //bellman-ford
{
int src = 0;
vector<bool> inq(size, false);
vector<int> dist(size, INF);
dist[src] = 0;
queue<int> q;
vector<int> count_q(size,0);
q.push(src);
inq[0] = true;
while (!q.empty())
{
int v = q.front();
q.pop();
inq[v] = false;
for (auto pr : adjListW[v])
{
int u = pr.first;
int weight = pr.second;
if (dist[v] != INF && dist[u] > dist[v] + weight)
{
dist[u] = dist[v] + weight;
if (!inq[u])
{
if(count_q[u]>size)
{
//o<<"Ciclu negativ!";
dist.clear();
return dist;
}
else
{
q.push(u);
inq[u]=true;
count_q[u]++;
}
}
}
}
}
/*for (int i = 1; i < size; i++)
if (dist[i] != INF)
o << dist[i] << " ";
else
o << 0 << " ";*/
for (int i = 1; i < size; i++)
if (dist[i] == INF)
dist[i]=0;
return dist;
}
int diameter() //diametru
{
int fnode;
int diameter = -1;
dfs_darb(0, diameter,fnode);
dfs_darb(fnode, diameter,fnode);
return diameter;
}
vector<int> eulerian_cycle(vector<int> &source, vector<int> &destination) //ciclueuler
{
vector<int> result;
vector<bool> usedEdge(size2, false);
stack<int> st;
for (int i = 0; i < size; i++)
{
if (adjList[i].size() % 2 == 1)
{
result.push_back(-1);
return result;
}
}
st.push(0);
while (!st.empty())
{
int node = st.top();
if (!adjList[node].empty())
{
int e = adjList[node].back();
adjList[node].pop_back();
if (!usedEdge[e])
{
usedEdge[e] = true;
int to = source[e] ^ destination[e] ^ node;
st.push(to);
}
}
else
{
st.pop();
result.push_back(node + 1);
}
}
return result;
}
pair<int, vector<int>> HopcroftKarp(vector<int> &toRight, vector<int> &toLeft, vector<int> &dist) //cuplaj
{
dist.resize(size + 1);
for (int u = 0; u <= size; u++)
toRight.push_back(0);
for (int v = 0; v <= size2; v++)
toLeft.push_back(0);
int count = 0;
while (hk_bfs(toRight, toLeft, dist))
{
for (int u = 1; u <= size; u++)
if (toRight[u] == 0 && hk_dfs(u, toRight, toLeft, dist))
count++;
}
return {count, toRight};
}
};
bool graphExists(vector<int> &v)
{
while (1)
{
sort(v.begin(), v.end(), greater<>());
if (!v[0])
return true;
int s = v[0];
v.erase(v.begin());
if (s > v.size())
return false;
for (int i = 0; i < s; i++)
{
v[i]--;
if (v[i] < 0)
return false;
}
}
}
class DisjointSets
{
int size,*rank,*parent;
public:
DisjointSets(int n)
{
size = n + 1;
rank=new int[size];
parent=new int[size];
for (int i = 1; i < size; i++)
{
parent[i] = i;
rank[i] = 1;
}
}
int Find(int x)
{
if (parent[x] == x)
return x;
return Find(parent[x]);
}
void Union(int x, int y)
{
int fx = Find(x);
int fy = Find(y);
if (rank[fx] <= rank[fy])
{
parent[fx] = fy;
rank[fy] += rank[fx];
}
else
{
parent[fy] = fx;
rank[fx] += rank[fy];
}
}
~DisjointSets()
{
delete[] parent;
delete[] rank;
}
};
class RoyFloydG
{
int size;
public:
int **matrix;
RoyFloydG(int n)
{
size = n;
matrix = new int *[size];
for (int i = 0; i < size; i++)
matrix[i] = new int[size];
}
void RoyFloyd()
{
int i, j, k;
for (k = 0; k < size; k++)
for (i = 0; i < size; i++)
for (j = 0; j < size; j++)
if (matrix[i][k] && matrix[k][j] && (matrix[i][j] > matrix[i][k] + matrix[k][j] || !matrix[i][j]) && i != j)
matrix[i][j] = matrix[i][k] + matrix[k][j];
}
~RoyFloydG()
{
for (int i = 0; i < size; i++)
delete[] matrix[i];
delete[] matrix;
}
};
void Solve_BFS()
{
int n, m, s;
int x, y;
f >> n >> m >> s;
Graph g(n,false);
for (int i = 1; i <= m; i++)
{
f >> x >> y;
g.addEdgeD(x - 1, y - 1);
}
vector<int> res=g.BFS(s - 1);
for(auto elem:res)
o<<elem<<" ";
}
void Solve_DFS()
{
int n, m;
int x, y;
f >> n >> m;
Graph g(n,false);
for (int i = 1; i <= m; i++)
{
f >> x >> y;
g.addEdgeU(x-1, y-1);
}
o << g.Connected();
}
void Solve_CTC()
{
int n, m;
int x, y;
f >> n >> m;
Graph g(n,false);
for (int i = 1; i <= m; i++)
{
f >> x >> y;
g.addEdgeD(x - 1, y - 1);
}
pair<int,vector<vector<int>>> res=g.SCC();
o << res.first << endl;
for (int i = 0; i < res.second.size(); i++)
{
for (int j = 0; j < res.second[i].size(); j++)
o << res.second[i][j] + 1 << " ";
o << endl;
}
}
void Solve_sortaret()
{
int n, m;
int x, y;
f >> n >> m;
Graph g(n,false);
for (int i = 1; i <= m; i++)
{
f >> x >> y;
g.addEdgeD(x - 1, y - 1);
}
vector<int> res=g.tS();
for(auto elem:res)
o<<elem<<" ";
}
void Solve_Havel_Hakimi()
{
int n, x;
vector<int> v;
f >> n;
for (int i = 0; i < n; i++)
{
f >> x;
v.push_back(x);
}
if (graphExists(v))
cout << "Da";
else
cout << "Nu";
}
void Solve_APM(){
int N, M;
int x, y, w;
f >> N >> M;
Graph g(N,true);
for (int i = 1; i <= M; i++)
{
f >> x >> y >> w;
g.addEdgeUW(x - 1, y - 1, w);
}
vector<pair<int,int>> res=g.MST();
o<<res[0].first<<endl;
o<<res[0].second<<endl;
for(int i=1;i<res.size();i++)
o<<res[i].first<<" "<<res[i].second<<endl;
}
void Solve_Dijkstra(){
int N, M;
int x, y, w;
f >> N >> M;
Graph g(N,true);
for (int i = 1; i <= M; i++)
{
f >> x >> y >> w;
g.addEdgeDW(x - 1, y - 1, w);
}
vector<int> res=g.Dijkstra();
for(int i=1;i<res.size();i++)
o<<res[i]<<" ";
}
void Solve_BellmanFord(){
int N, M;
int x, y, w;
f >> N >> M;
Graph g(N,true);
for (int i = 1; i <= M; i++)
{
f >> x >> y >> w;
g.addEdgeDW(x - 1, y - 1, w);
}
vector<int> res=g.BellmanFord();
if(res.empty())
o<<"Ciclu negativ!";
else
for(int i=1;i<res.size();i++)
o<<res[i]<<" ";
}
void Solve_disjoint(){
int N, M;
int cod, x, y;
f >> N >> M;
DisjointSets ds(N);
for (int i = 1; i <= M; i++)
{
f >> cod >> x >> y;
if (cod == 1)
ds.Union(x, y);
else if (ds.Find(x) == ds.Find(y))
o << "DA\n";
else
o << "NU\n";
}
}
void Solve_darb(){
int N, x, y;
f >> N;
Graph g(N,false);
for (int i = 1; i <= N - 1; i++)
{
f >> x >> y;
g.addEdgeU(x - 1, y - 1);
}
o << g.diameter();
}
void Solve_royfloyd(){
int N;
f >> N;
RoyFloydG g(N);
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
f >> g.matrix[i][j];
g.RoyFloyd();
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
o << g.matrix[i][j] << " ";
o << endl;
}
}
void Solve_ciclueuler()
{
vector<int> source, destination;
int N, M, x, y;
f >> N >> M;
Graph g(N, M,false);
for (int i = 0; i < M; i++)
{
f >> x >> y;
g.addEdgeMultigraph(x - 1, y - 1, i, source, destination);
}
vector<int> result = g.eulerian_cycle(source, destination);
if (result[0] == -1)
o << -1;
else
for (int i = 0; i < M; i++)
o << result[i] << ' ';
}
void Solve_cuplaj()
{
int N, M, E;
f >> N >> M >> E;
Graph g(N, M,true);
int x, y;
for (int i = 1; i <= E; i++)
{
f >> x >> y;
g.addEdgeD(x, y);
}
vector<int> toRight, toLeft, dist;
pair<int, vector<int>> res = g.HopcroftKarp(toRight, toLeft, dist);
o << res.first << endl;
for (int i = 1; i <= N; i++)
if (res.second[i])
o << i << " " << res.second[i] << endl;
}
int main()
{
//Solve_BFS();
//Solve_DFS();
//Solve_CTC();
//Solve_sortaret();
//Solve_Havel_Hakimi();
//Solve_APM();
//Solve_Dijkstra();
//Solve_BellmanFord();
//Solve_disjoint();
Solve_darb();
//Solve_royfloyd();
//Solve_ciclueuler();
//Solve_cuplaj();
return 0;
}