Largest cycle in a tree

You are given a tree of $N$ nodes and $N-1$ edges. Now you need to select two nodes $a$ and $b$ in the tree such that the cycle that will be formed after adding an edge between the two nodes $a$ and $b$, its length should be maximum. If there is more than one possible answer, you can output any of them.

Example:

Input:  N = 7, edges = {{1, 2}, {1, 3}, {2, 4}, {2, 5}, {3, 6}, {3, 7}}
Output: 4 6

Approach

C++

#include <bits/stdc++.h>
using namespace std;

vector<int> adj[100001];

int N;
pair<int, int> bfs(int u)
{
    queue<int> q;
    int dist[N + 1];
    memset(dist, -1, sizeof(dist));

    q.push(u);

    while (!q.empty())
    {
        u = q.front();
        q.pop();

        for (auto i : adj[u])
        {
            if (dist[i] == -1)
            {
                dist[i] = dist[u] + 1;
                q.push(i);
            }
        }
    }

    int maxDist = 0, node;

    for (int i = 1; i <= N; i++)
    {
        if (dist[i] > maxDist)
        {
            maxDist = dist[i];
            node = i;
        }
    }
    return make_pair(node, maxDist);
}

pair<int, int> largestCycle(vector<vector<int>> edges)
{
    //create the graph
    for (int i = 0; i < edges.size(); i++)
    {
        int u = edges[i][0];
        int v = edges[i][1];

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    pair<int, int> node1, node2;
    node1 = bfs(1);

    node2 = bfs(node1.first);

    return make_pair(node1.first, node2.first);
}
int main()

{

    N = 7;

    vector<vector<int>> edges = {{1, 2},
                                 {1, 3},
                                 {2, 4},
                                 {2, 5},
                                 {3, 6},
                                 {3, 7}};

    pair<int, int> res = largestCycle(edges);

    cout << res.first << " " << res.second << "\n";

    return 0;
}