class Solution {
public:
    vector<int> clr;
    vector<int> dis;
    vector<int> newVisitedNodes;
    vector<vector<int>> graph;

    bool hasBipartiteSplit(int node) {
        newVisitedNodes.clear();
        bool hasSplit;

        newVisitedNodes.push_back(node);
        queue<int> q;
        q.push(node);
        clr[node] = 0;
        dis[node] = 0;
        while(q.size()) {
            int curNode = q.front();
            int curClr = clr[curNode];
            int nextClr = curClr ^ 1;
            for(auto nbr: graph[curNode]) {
                if(clr[nbr] == -1) {
                    clr[nbr] = nextClr;
                    q.push(nbr);
                    newVisitedNodes.push_back(nbr);
                    dis[nbr] = dis[curNode] + 1;
                } else if(clr[nbr] != nextClr) {
                    return 0;
                }
            }
            q.pop();
        }
        return true;
    }

    int getMaximumSplits(int node) {
        for(auto &newNodes : newVisitedNodes) {
            dis[newNodes] = -1;
        }
        queue<int> q;
        q.push(node);
        dis[node] = 0;
        int farthestNodeDistance = -1;
        while(q.size()) {
            int curNode = q.front();
            farthestNodeDistance = max(farthestNodeDistance, dis[curNode]);
            for(auto nbr: graph[curNode]) {
                if(dis[nbr] == -1) {
                    q.push(nbr);
                    dis[nbr] = dis[curNode] + 1;
                }
            }
            q.pop();
        }

        return farthestNodeDistance + 1;

    }
    int magnificentSets(int n, vector<vector<int>>& edges) {
        int ans = 0;
        clr = vector<int>(n+1,-1);
        dis = vector<int>(n+1,-1);
        graph = vector<vector<int>>(n+1);
        for(auto &edge: edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
        for(int i = 1 ; i <=  n ;i++) {
            if(dis[i] == -1) {
                if(hasBipartiteSplit(i)) {
                    int mx = -1;
                    for(auto & newNode : newVisitedNodes) {
                        mx = max(mx, getMaximumSplits(newNode));
                    }
                    ans += mx;
                } else {
                    return -1;
                }
            }
        }

        return ans;
    }
};