题解：CF2029D Cool Graph

通过把玩操作可以发现，我们可以试图构造以 1 为根的树。

首先对边操作，只要把和 1 不相关的边都删掉，然后对点操作，使得所有点都和 1 相连即可。

做多操作 m+n 次，时间复杂度 O(m+n)。

const int N=2e5+9;
int T, n, m, k, q;
int v, u, b[N];

void solve() {
    vector<int> A;
    cin >> n >> m;
    for(int i=1; i<=n; i++) b[i] = 0;
    for(int i=1; i<=m; i++) {
        cin >> u >> v;
        if(u!=1 && v!=1) {  // 所有不是1的点就操作
            A.push_back(1);
            A.push_back(u);
            A.push_back(v);
        }
        b[u]^= 1;  // 记录点的度数，如果是奇数，说明点和1有边。对点操作时就可以跳过。
        b[v]^= 1;
    }

    int p = 0;
    for(int i=2; i<=n; i++) if(b[i]) {p = i; break;}

    if(p) for(int i=2; i<=n; i++){ //对点操作
        if(!b[i]) {
            A.push_back(1);
            A.push_back(p);
            A.push_back(i);
            p = i;
        }
    }

    cout<< A.size()/3 << "\n";
    for(int i=0; i<A.size(); i++) cout << A[i] << "  \n"[i%3];
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> T; while(T--)
        solve ();
    return 0;
}