题目链接:https://codeforces.com/contest/405/problem/E

题解:可知mm为奇数是必然无解输出No solution.

那么当mm为偶数的情况是必然有解的。为何?

我自己想的证明是:由于图是连通的且不存在自环,且此时边数为偶数。在某个匹配下,由于mm是偶数,那么必然存在两条边无法匹配,那么对于这两条边,他们必然是连通的。那么必然可以通过切换边的匹配来找到另一种方案使得匹配一定完成。

既然知道必然匹配,要怎么匹配? 那么考虑u,v,zu,v,z三个点,假设对于vv而言他的子节点个数若为偶数个,说明对于v而言可以完全匹配,那么只需要将vv作为待匹配点返回uu,
假设为奇数个,那么必然存在一个点,使得无法匹配,那么此时就必然要用到(u,v)(u,v)这条边。如此即可。

#include <bits/stdc++.h>
#define pa pair<int, int>
#define mp make_pair
#define lowbit(x) ((x)&(-x))
#define mem(i, a) memset(i, a, sizeof(i))
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 5;
struct edge {
    int u,v,next;
}e[N * 2];
int head[N],vis[N];
int n,m,cnt;
void insert(int u, int v) {
    e[cnt].u = u; e[cnt].v = v; e[cnt].next = head[u]; head[u] = cnt++;
}
int dfs(int u, int fa) {
    queue<int> q;
    for(int i = head[u]; i != -1 ; i = e[i].next) {
        int v = e[i].v;
        if(v == fa || vis[i]) continue;
        vis[i] = vis[i ^ 1] = 1;
        int jud = dfs(v, u);
        if(jud) {
            cout << u <<" " << v << " " << jud << "\n";
        } else {
            q.push(v);
        }
    }
    while(q.size() >= 2) {
        int x = q.front(); q.pop();
        int y = q.front(); q.pop();
        cout << x << " " << u << " " << y << "\n";
    }
    if(!q.empty()) {
        int x = q.front(); q.pop();
        return x;
    }
    return 0;
}
int main() {
    mem(head, -1);
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u,v;
        scanf("%d %d", &u, &v);
        insert(u, v); insert(v, u);
    }
    if(m & 1) {
        cout << "No solution"; return 0;
    } else dfs(1, -1);
    return 0;
}