class Solution {
public:
    int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
        vector<vector<int>> gr(n+1);
        vector<int> indegree(n+1, 0), prev_time(n+1, 0);
        for(auto& edge : relations){
            gr[edge[0]].push_back(edge[1]);
            indegree[edge[1]]++;
        }
        time.insert(time.begin(), 0);
        queue<int> q;
        for(int i =1; i <= n; i++)
            if(indegree[i] == 0)
                q.push(i);
        while(!q.empty()){
            int node = q.front();q.pop();
            for(auto adjV : gr[node]){
                prev_time[adjV] = max(prev_time[adjV] , time[node] + prev_time[node]);
                if(--indegree[adjV] == 0)
                    q.push(adjV);
            }
        }
        int ans = 0;
        for(int i =1 ; i < n + 1; ++i){
            ans = max(ans, time[i]+prev_time[i]);
        }
        return ans;
    }
};

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        vector<vector<int>> graph(n);
        vector<int> indegree(n, 0), ans;

        for(auto e : edges){
            graph[e[0]].push_back(e[1]);
            graph[e[1]].push_back(e[0]);
            indegree[e[0]]++;
            indegree[e[1]]++;
        }
        queue<int> q;
        for(int i = 0; i < n ;i++)
            if(indegree[i] == 1)
                q.push(i), indegree[i]--;
        
        while(!q.empty()){
            int s = q.size();
            ans.clear();
            for(int i = 0 ; i < s ;i++){
                int curr = q.front(); q.pop();
                ans.push_back(curr);
                for(auto child : graph[curr])
                {
                    indegree[child]--;
                    if(indegree[child] == 1)
                        q.push(child);
                }
            }
        }
        if(n == 1)ans.push_back(0);
        return ans;
    }
};