Centroid

#include <bits/stdc++.h>
#define MAX 100007

using namespace std;

vector<int> graph[MAX];
struct Centroid {
    int vis[MAX], siz[MAX], root;
    int parent[MAX], layer[MAX];

    vector<int> tree[MAX];

    void init(){
        for(int i = 0; i < MAX; i++){
            vis[i] = siz[i] = layer[i] = parent[i] = 0;
            tree[i].clear();
        }
    }

    int getCent(int u, int n, int p = 0){
        for(int v: graph[u]){
            if(!vis[v] && v != p && siz[v] > n/2) return getCent(v, n, u);
        }

        return u;
    }
    int find(int u, int p = 0){
        siz[u] = 1;
        for(int v: graph[u]){
            if(v != p && !vis[v]){
                find(v, u);
                siz[u] += siz[v];
            }
        }

        return p? 0: getCent(u, siz[u]);
    }

    void build(int u = 0){
        if(u == 0){
            u = root = find(1);
            vis[u] = 1;
            layer[u] = 1;
        }

        for(int v: graph[u]){
            if(!vis[v]){
                int x = find(v);
                vis[x] = 1;
                layer[x] = layer[u] + 1;
                parent[x] = u;

                tree[u].push_back(x);
                tree[x].push_back(u);
                build(x);
            }
        }
    }

    vector<int> operator[](int i)const{
        return tree[i];
    }
} c;

int vis[MAX], parent[LOG][MAX];
void bfs(int no){

}
int main(){
    c.init();
    int n, m; cin >> n >> m;
    while(m--){
        int a, b; cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    cout << "oi\n";
    c.build();
    cout << "ola\n";
    bfs(c.root);
    return 0;
}