「CF858F」Wizard's Tour

Description

给定一张 nn 个点 mm 条边的无向图,每条边连接两个顶点,保证无重边自环,不保证连通。
你想在这张图上进行若干次旅游,每次旅游可以任选一个点 xx 作为起点,再走到一个与 xx 直接有边相连的点 yy,再走到一个与 yy 直接有边相连的点 zz 并结束本次旅游。
作为一个旅游爱好者,你不希望经过任意一条边超过一次,注意一条边不能即正向走一次又反向走一次,注意点可以经过多次,在满足此条件下,你希望进行尽可能多次的旅游,请计算出最多能进行的旅游次数并输出任意一种方案。

Input

The first line contains two integers n, m (1 ≤ n ≤ 2·105, 0 ≤ m ≤ 2·105) — the number of cities and the number of roads in Berland, respectively.

The roads description follow, one in each line. Each description is a pair of two integers ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi), where ai and bi are the ids of the cities connected by the i-th road. It is guaranteed that there are no two roads connecting the same pair of cities. Every road is bidirectional. The cities are numbered from 1 to n.

It is possible that the road network in Berland is not connected.

Output

In the first line print w — the maximum possible number of episodes. The next w lines should contain the episodes in format x, y, z — the three integers denoting the ids of the cities in the order of the wizard’s visits.

Sample Input

1
2
3
4
5
6
4 5
1 2
3 2
2 4
3 4
4 1

Sample Output

1
2
3
2
1 4 2
4 3 2

Solution

roz(Bill Yang)
简化问题,首先考虑一棵树的情况:

如果当前结点有偶数个子结点,那么为了让方案数最多,肯定两两配对。

如果是奇数个子结点,那么两两配对后就会剩下一个结点,我们把剩下的这个结点和fa结点配对即可,如图:

如果是一个图怎么办?
我们尽量地将图转化成树用刚才的方式处理,Tarjan不就是将图转化成树的算法?
借鉴Tarjan的思想,我们考虑有环的情况,边分为父子边和返祖边,父子边和树是一样的处理方法,返祖边呢,把返祖的祖先结点当作儿子结点处理即可。

当前点的所有能连接的点都一一配对。

  • 如果多出来,答案就是(fa,u,z)(保证多出来的一定用掉)
  • 如果没多出来,就直接把(fa,u)加到tmp里(留给自己或者父亲用)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

const int N = 3e5*2, M = 3e5*2;
struct Edge {
int u, v, nxt;
}e[M];
int head[N], en;
void addedge(int x, int y) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en;
}
int n, m;
int dfn[N], num;
bool vis[N];
struct Ans{
int x, y, z;
};
vector<Ans>ans;
int dfs(int x, int fro) {
dfn[x] = ++num;
vis[x] = 1;
vector<int>tmp;
for(int i = head[x]; i;i = e[i].nxt) if((i ^ 1) != fro){
int y = e[i].v;
if(!dfn[y]) {
int z = dfs(y, i);
if(~z) ans.pb((Ans){x, y, z});
else tmp.pb(y);
} else if(vis[y] && dfn[y] < dfn[x]) {
tmp.pb(y);
}
}
for(int i = 1; i < tmp.size(); i += 2) ans.pb((Ans){tmp[i - 1], x, tmp[i]});
if(tmp.size() % 2)
return tmp.back();
return -1;
}

int main() {
n = read(), m = read();
en = 1;
for(int i = 1; i <= m; ++i) {
int x = read(), y = read();
addedge(x, y);
addedge(y, x);
}
for(int i = 1; i <= n; ++i )if(!dfn[i]) dfs(i, 0);
writeln(ans.size());
for(int i = 0; i < ans.size(); ++i)
printf("%d %d %d\n", ans[i].x, ans[i].y, ans[i].z);
return 0;
}