GATE CSE 2025 Session 2 Q59: Output of the double-BFS algorithm on a given tree

Consider the following algorithm someAlgo that takes an undirected graph $G$ as input.

someAlgo($G$)

1. Let $v$ be any vertex in $G$. Run BFS on $G$ starting at $v$. Let $u$ be a vertex in $G$ at maximum distance from $v$ as given by the BFS.

2. Run BFS on $G$ again with $u$ as the starting vertex. Let $z$ be the vertex at maximum distance from $u$ as given by the BFS.

3. Output the distance between $u$ and $z$ in $G$.