A graph which is connected and acyclic can be considered a tree. The hight of the tree depends on the selected root. Now you are supposed to find the root that results in a highest tree. Such a root is called the deepest root.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤10​4​​) which is the number of nodes, and hence the nodes are numbered from 1 to N. Then N−1 lines follow, each describes an edge by given the two adjacent nodes' numbers.

Output Specification:

For each test case, print each of the deepest roots in a line. If such a root is not unique, print them in increasing order of their numbers. In case that the given graph is not a tree, print Error: K components where K is the number of connected components in the graph.

Sample Input 1:

5

1 2

1 3

1 4

2 5

Sample Output 1:

3

4

5

Sample Input 2:

5

1 3

1 4

2 5

3 4

Sample Output 2:

Error: 2 components

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#include <algorithm>

#include <iostream>

#include <string.h>

#include <queue>

#include <string>

#include <set>

#include <map>

using namespace std;

const int maxn = ;

const int inf = ;

int n;

int depth[maxn] = {  };

bool vis[maxn] = { false };

struct node {

    int id;

    int depth;

}nodes[maxn];

vector<int> adj[maxn];

void bfs(int v) {

    queue<node> q;

    q.push(nodes[v]);

    vis[v] = true;

    while (!q.empty()) {

        node u = q.front();

        q.pop();

        for (int i = ; i < adj[u.id].size(); i++) {

            if (vis[adj[u.id][i]] == false) {

                nodes[adj[u.id][i]].depth = u.depth + ;

                q.push(nodes[adj[u.id][i]]);

                vis[adj[u.id][i]] = true;

                if (nodes[adj[u.id][i]].depth > depth[v]) {

                    depth[v] = nodes[adj[u.id][i]].depth;

                }

            }

        }

    }

}

bool bfs_c(int v) {

    fill(vis, vis + maxn, false);

    queue<int> q;

    q.push(v);

    vis[v] = true;

    int count = ;

    while (!q.empty()) {

        int u = q.front();

        q.pop();

        vis[u] = true;

        for (int i = ; i <adj[u].size(); i++) {

            if (vis[adj[u][i]] == false) {

                q.push(adj[u][i]);

                count++;

                if (count > n)return false;

            }

        }

    }

    return true;

}

int bfsTrave() {

    fill(vis, vis + maxn, false);

    int count = ;

    for (int i = ; i <= n; i++) {

        if (vis[i] == false) {

            bfs(i);

            count++;

        }

    }

    return count;

}

int main() {

    cin >> n;

    for (int i = ; i < n; i++) {

        int c1, c2;

        cin >> c1 >> c2;

        adj[c1].push_back(c2);

        adj[c2].push_back(c1);

    }

    for(int i=;i<=n;i++){

        nodes[i].id = i;

        nodes[i].depth = ;

    }

    int k = bfsTrave();

    if (k > )printf("Error: %d components", k);

    else {

        if (!bfs_c())printf("Error: %d components", k);

        else {

            for (int i = ; i <= n; i++) {

                fill(vis, vis + maxn, false);

                for (int i = ; i <= n; i++) {

                    nodes[i].depth = ;

                }

                bfs(i);

            }

            int max_d = ;

            vector<int> maxi;

            for (int i = ; i <= n; i++) {

                if (depth[i] > max_d) {

                    max_d = depth[i];

                    maxi.clear();

                    maxi.push_back(i);

                }

                else if (depth[i] == max_d) {

                    maxi.push_back(i);

                }

            }

            for (int i = ; i < maxi.size(); i++) {

                printf("%d\n", maxi[i]);

            }

        }

    }

    system("pause");

}