官方题解给的线段树做法常数小但是难写，这里给出一种我自己实现的一种常数大的基于各种 STL 进行模拟的做法。

首先除了记录各个节点的度之外，还需要记录每个点邻接的、存在特殊性质的点的个数，包括：

• 度为 1 的邻接点（规约规则用）
• 度为 2 的邻接点（贪心规则用，“删掉之后剩余度为 1 的点”最多等价于“当前邻接点度为 2 减去当前邻接点度为 1 个数最多的点”）

接下来我们使用一个 set 来维护当前点集的信息，并根据规约规则和贪心规则确定删除点的优先级。用可删除堆也能维护，但是 set 还是比较稳定不会出错的。

接下来删除每个节点的时候，显然用 unordered_map 数组记录图结构能满足修改图结构的复杂度。此外删除每个点时，还需要修改对应邻接点的各个信息，我不太记得具体实现细节要怎么写了，反正推推推写写写就行了。

最后注意，在删除度为 1 的点时，要同时删除唯一邻接点。为了实现方便（不要把信息更新这一坨复制一遍），我这里控制了一下是否要进行递归删除，显然递归到邻接点就是底层了。

时间复杂度是常数巨大的 $O((n+m)\log n)$，要跑将近 1s 的时间。

#include <stdio.h>
#include <queue>
#include <set>
#include <unordered_set>
#define getchar getchar_unlocked
#define putchar putchar_unlocked
inline int rd()
{
    int k = 0;
    char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') k = k * 10 + (c ^ '0'), c = getchar();
    return k;
}
inline void wr(int x)
{
    if (x > 9) wr(x / 10);
    putchar((x % 10) ^ '0');
}

const int N = 114514;
int n, m, u, v;
int deg[N], adj2[N], adj1[N];
bool del[N];
std::unordered_set<int> g[N]; // origin edge

inline void add_edge(int u, int v) { g[u].insert(v), g[v].insert(u), ++deg[u], ++deg[v]; }

struct info
{
    int id, deg, adj;
    info(int u = 0, int d = 0, int cnt = 0) : id(u), deg(d), adj(cnt) {}
    inline bool operator<(const info& o) const
    {
        if (deg < 2 && o.deg >= 2) return 1;
        else if (deg >= 2 && o.deg < 2) return 0;
        else if (deg < 2 && o.deg < 2) return (deg ^ o.deg) ? (deg < o.deg) : (id < o.id);
        else return (deg ^ o.deg) ? (deg > o.deg) : (adj ^ o.adj) ? (adj > o.adj) : (id > o.id);
    }
};
std::set<info> s;

inline void init()
{
    for (int u = 1; u <= n; ++u)
        if (deg[u] == 2) 
            for (auto& v : g[u]) ++adj2[v];
        else if (deg[u] == 1)
            for (auto& v : g[u]) ++adj1[v];
    for (int u = 1; u <= n; ++u) s.insert(info(u, deg[u], adj2[u] - adj1[u]));
}
inline void change(int u, bool rec = 1)
{
    std::vector<int> change_deg;
    change_deg.reserve(g[u].size());

    if (deg[u] <= 1 && rec) wr(u), putchar('\n');

    del[u] = 1, s.erase(s.lower_bound(info(u, deg[u], adj2[u] - adj1[u])));
    for (auto& v : g[u]) g[v].erase(u), change_deg.push_back(v);
    std::vector<int> add_adj2, sub_adj2, add_adj1, sub_adj1;
    for (auto& v : change_deg)
    {
        if (deg[u] == 2) sub_adj2.push_back(v);
        else if (deg[u] == 1) sub_adj1.push_back(v);

        if (deg[v] == 3) for (auto& w : g[v]) add_adj2.push_back(w);
        else if (deg[v] == 2) for (auto& w : g[v]) add_adj1.push_back(w);
        else if (deg[v] == 1) for (auto& w : g[v]) sub_adj1.push_back(w);
    }
    g[u].clear(), deg[u] = adj1[u] = adj2[u] = 0;
    for (auto& v : change_deg)
    {
        s.erase(s.lower_bound(info(v, deg[v], adj2[v] - adj1[v]))), --deg[v];
        s.insert(info(v, deg[v], adj2[v] - adj1[v]));
    }
    for (auto& v : add_adj2)
    {
        s.erase(s.lower_bound(info(v, deg[v], adj2[v] - adj1[v]))), ++adj2[v];
        s.insert(info(v, deg[v], adj2[v] - adj1[v]));
    }
    for (auto& v : sub_adj2)
    {
        s.erase(s.lower_bound(info(v, deg[v], adj2[v] - adj1[v]))), --adj2[v];
        s.insert(info(v, deg[v], adj2[v] - adj1[v]));
    }
    for (auto& v : add_adj1)
    {
        s.erase(s.lower_bound(info(v, deg[v], adj2[v] - adj1[v]))), --adj2[v], ++adj1[v];
        s.insert(info(v, deg[v], adj2[v] - adj1[v]));
    }
    for (auto& v : sub_adj1)
    {
        s.erase(s.lower_bound(info(v, deg[v], adj2[v] - adj1[v]))), --adj1[v];
        s.insert(info(v, deg[v], adj2[v] - adj1[v]));
    }
    if (change_deg.size() == 1 && rec) change(change_deg[0], 0);
}
int main()
{
    n = rd(), m = rd();
    while (m--) u = rd(), v = rd(), add_edge(u, v);
    init();
    while(s.size()) change(s.begin()->id);
}