class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<vector<int>> &edges) {
vector<vector<int>> g(n);
vector<int> d(n);
for (auto e:edges) {
int a = e[0], b = e[1];
g[a].push_back(b), g[b].push_back(a);
d[a]++, d[b]++;
}
queue<int> q, tmp;
for (int i = 0; i < n; i++) {
if (d[i] <= 1)q.push(i);
}
while (q.size()) {
tmp = q;
queue<int> nxt;
while (q.size()) {
int u = q.front();
d[u]--;
q.pop();
for (auto i:g[u]) {
if (--d[i] == 1)nxt.push(i);
}
}
q = nxt;
}
vector<int> res;
while (tmp.size()) {
res.push_back(tmp.front());
tmp.pop();
}
return res;
}
};
