目前最优解。

此题解可以说是 这篇题解 的拓展，思路几乎一致，唯一不同点是可过已知 hack，正确性更有保证吧。欢迎大家前来 hack ！

Solution

在某一轮中，称两个点被染上同一种颜色且它们在原图上有连边为“连边”。（借用一下 这篇题解 的话 /kel）

链的构造

奇数轮连边 $(0, 1), (2, 3), (4, 5),\cdots$，偶数轮连边 $(1, 2), (3, 4), (5, 6),\cdots$ 即可。

正确性显然。

树的构造

注意：根节点 $rt$ 的深度为 $0$。

首先我们预先选好一个 $rt$ 的儿子 $son$。

仿照链的做法，我们考虑奇数轮将所有深度为奇数的点与其父亲连边即可。所有深度为偶数的点与其父亲连边。但在每一轮，我们都将 $rt$ 与 $son$ 连边。

这样我们发现，除了根节点外的其他点，要么先走到一个叶子节点，然后只会向上走，直到走到 $rt$，最后就在 $(rt, son)$ 这条边上不停循环，总步数 $\le 2n$。证明的话就分讨一下到达 $rt$ 的奇偶性即可。

所以对于任意一对不是根节点的初始点 $(x, y)$，我们都能满足最后在 $(rt, son)$ 上相遇。

但对于根节点，我们发现，它可以随时逃到 $son$ 上，然后逃往其他节点，这就可能使两点不能相遇。对于另一个初始点为 $son$ 子树内的，我们不用担心。但对于另一个点不是 $son$ 子树内的，我们发现，若将最后两点所走过的所有的点找出来，则一定是一条链，长度 $\le n$，每个点最多被走 $2$ 次，所以总次数 $\le 2n$。构造成立！

一般图的构造

对于树的构造，我们发现只要满足以下条件就能套用到图上：

• 对于任意一个点 $u$，都满足其儿子之间没有边。

• 存在一个根节点 $rt$，满足存在一个儿子 $son$，$son$ 的所有儿子与 $rt$ 之间不存在边。

第一个条件直接求 dfs 树即可满足，问题是第二个条件。

我们以任意一个点为根节点 $rt'$，找出一颗 dfs 树，然后我们找到最深的一个节点 $u$ 满足，在 dfs 树上，其每个儿子的子树都是一条链，简单来说 $u$ 就是深度最大的分叉点。设 $u$ 的父亲为 $f$。

若存在一个 $u$ 的儿子 $v$ 满足 $v$ 和 $f$ 之间没有边，则可以从 $v$ 开始重新 dfs，并且先 $v \rightarrow u \rightarrow f$，然后选 $rt = v, son = u$ 即可。

若没有一个儿子满足，则任取两个不同的儿子 $v$ 和 $v'$，然后从 $v$ 开始重新 dfs，并且先 $v \rightarrow u \rightarrow v'$，$rt = v, son = u$ 即可。

但问题在于，$v$ 的儿子可能与 $u$ 有连边，那么此时就可能不满足条件二。

但因为 $u$ 是深度最深的分叉点，所以 $v$ 的子树是一条链。我们考虑可以先将这条链删去，然后跑树的做法，最后再单独跑这条链。具体的，我们将 $v$ 的子树内除 $v$ 的点都临时删掉，然后跑树的构造。跑完后，我们将除了 $w,v$ 的其他点都删掉，再将链加回来，显然此时整个图还是一条链，然后我们跑链的构造即可（原因是非根节点跑完树后，起始点一定在 $rt$ 或 $son$ 上）。

当然，这个做法在一个初始点是根节点的时候会寄，但我们考虑，先在一开始跑个 $v$ 与其子树构成的链的构造即可，当然一定要满足 $v$ 跑完后回到 $v$，才能再跑树的。

所以总的次数粗略估计 $\le 6n$ 的，显然可过。但精细算一下，实现的精细一点，其实是 $\le 4n$ 的，因为就是直径长度 $\times 2$ 再加上一条链的长度 $\times 2$，显然最大 $4n$。

:::success[AC Code]

#include <bits/stdc++.h>
using namespace std;
#define x first
#define mp(Tx, Ty) make_pair(Tx, Ty)
#define For(Ti, Ta, Tb) for(auto Ti = (Ta); Ti <= (Tb); Ti++)
#define Dec(Ti, Ta, Tb) for(auto Ti = (Ta); Ti >= (Tb); Ti--)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
const int N = 105;
int n, m;
int u[N * N], v[N * N];
namespace Sub1 {
	void work() {
		if (m != n - 1) return;
		For(i, 1, m) if (u[i] != 0 && v[i] != 0) return;
		cout << n * 2 - 1 << '\n';
		For(j, 1, n) cout << 0 << ' ';
		cout << '\n';
		For(i ,1, m) {
			For(j, 0, n - 1) {
				if (j == u[i] || j == v[i]) cout << 1 << ' ';
				else cout << 0 << ' ';
			}
			cout << '\n';
			For(j, 0, n - 1) {
				if (j == u[i] || j == v[i]) cout << 1 << ' ';
				else cout << 0 << ' ';
			}
			cout << '\n';
		} 
		exit(0);
	}
} 
namespace Sub2 { 
	int h[N], e[N * N * 2], ne[N * N * 2], idx;
	void add(int a, int b) {
		e[idx] = b, ne[idx] = h[a], h[a] = idx++;
	}
	int in[N];
	bool is[N * N * 2];
	int fa[N];
	int dep[N];
	bool vis[N];
	bool ban[N];
	int cnttt;
	void dfs(int x, int father, int S, int S1, int op) {
		if (op && ban[x]) return;
		fa[x] = father;
		vis[x] = 1;
		if (father == -1 && S != -1) dep[S] = dep[x] + 1, dfs(S, x, S, S1, op);
		if (x == S && S1 != -1) dep[S1] = dep[x] + 1, dfs(S1, x, S, S1, op);
		for (int i = h[x]; ~i; i = ne[i]) {
			int j = e[i];
			if (!op && !is[i]) continue;
			if (j == father) continue;
			if (vis[j]) continue;
			dep[j] = dep[x] + 1;
			dfs(j, x, S, S1, op); 
		}
	}
	int c[N];
	void work(int rt, int son, int son1, int op) {
//		cout << rt << ' ' << son << ' ' << son1 << '\n';
//		For(i, 0, n - 1) cout << ban[i] << ' ';
//		cout << '\n';
		if (op) {
			memset(vis, 0, sizeof(vis));
			memset(dep, 0, sizeof(dep));
			memset(fa, 0, sizeof(fa));
			dfs(rt, -1, -1, -1, 0);
			ban[rt] = 1;
			cout << n * 2 + (cnttt * 2 + 1) * 2 << '\n';
			For(i, 1, cnttt * 2 + 1) {
				int flag = (i & 1);
				int C = 0;
				For(k, 0, n - 1) c[k] = k;
				For(k, 0, n - 1) {
					if (!ban[k]) continue;
					if ((dep[k] & 1) == flag) {
						if (fa[k] != -1) {
							if (c[fa[k]] != fa[k]) c[k] = c[fa[k]];
							else c[fa[k]] = c[k] = k;
						}
					}
				}
				For(i, 0, n - 1) cout << c[i] << ' ';
				cout << '\n';
			}
			ban[rt] = 0;
		}
		if (!op) cout << n * 2 << '\n';
		memset(vis, 0, sizeof(vis));
		memset(dep, 0, sizeof(dep));
		memset(fa, 0, sizeof(fa));
		dfs(rt, -1, son, son1, op);
		For(i, 1, n * 2) {
			int flag = (i & 1);
			int C = 0;
			For(k, 0, n - 1) c[k] = k;
			For(k, 0, n - 1) {
				if (ban[k]) continue;
				if ((dep[k] & 1) == flag) {
					if (fa[k] != -1) {
						if (c[fa[k]] != fa[k]) c[k] = c[fa[k]];
						else c[fa[k]] = c[k] = k;
					}
				}
			}
			if (op) c[rt] = c[son];
			For(i, 0, n - 1) cout << c[i] << ' ';
			cout << '\n';
		}
		if (op) {
			memset(vis, 0, sizeof(vis));
			memset(dep, 0, sizeof(dep));
			memset(fa, 0, sizeof(fa));
			dfs(son, -1, -1, -1, 0);
			ban[son] = ban[rt] = 1;
			For(i, 1, cnttt * 2 + 1) {
				int flag = (i & 1);
				int C = 0;
				For(k, 0, n - 1) c[k] = k;
				For(k, 0, n - 1) {
					if (!ban[k]) continue;
					if ((dep[k] & 1) == flag) {
						if (fa[k] != -1) {
							if (c[fa[k]] != fa[k]) c[k] = c[fa[k]];
							else c[fa[k]] = c[k] = k;
						}
					}
				}
				For(i, 0, n - 1) cout << c[i] << ' ';
				cout << '\n';
			}
		}
		exit(0);
	}
	void dfs1(int x, int father) {
		fa[x] = father;
		vis[x] = 1;
		for (int i= h[x]; ~i; i = ne[i]) {
			int j = e[i];
			if (j == father) continue;
			if (vis[j]) continue;
			is[i] = is[i ^ 1] = 1;
			dep[j] = dep[x] + 1;
			dfs1(j, x);
			in[j]++;
			in[x]++;
		}
	}
	void find(int x, int fa) {
		ban[x] = 1;
		cnttt++;
		for (int i = h[x]; ~i; i = ne[i]) {
			if (!is[i]) continue;
			int j = e[i];
			if (j == fa) continue;
			find(j, x); 
		}
	}
	void solve(int rt) {
		cnttt = 0;
		memset(h, -1, sizeof(h));
		memset(vis, 0, sizeof(vis));
		memset(dep, 0, sizeof(dep));
		memset(is, 0, sizeof(is));
		memset(in, 0, sizeof(in));
		memset(fa, 0, sizeof(fa));
		memset(ban, 0, sizeof(ban));
		idx = 0;
		For(i, 1, m) add(u[i], v[i]), add(v[i], u[i]);
		dfs1(rt, -1);
		int cnt = 0;
		bool f = 1;
		int rtt = rt;
		For(i, 0, n - 1) {
			if (in[i] == 1) cnt++, rtt = i;
			if (in[i] > 2) f = 0;
		}
		if (cnt == 2 && f) work(rtt, -1, -1, 0);
		int w = -1;
		For(i, 0, n - 1) {
			if (i != rt && in[i] > 2) {
				if (w == -1) w = i;
				else if (dep[w] < dep[i]) w = i;
			}
		}
		if (w == -1) {
			for (int i = h[rt]; ~i; i = ne[i]) {
				if (!is[i]) continue;
				int j = e[i];
				solve(j);
			}
		}
		for (int i = h[w]; ~i; i = ne[i])	{ 
			if (!is[i]) continue;
			int j = e[i];
			if (j == fa[w]) continue;
			bool f = 1;
			for (int ii = h[j]; ~ii; ii = ne[ii]) {
				int jj = e[ii];
				if (jj == fa[w]) {
					f = 0;
					break;
				}
			}
			if (f) {
				find(j, w);
				ban[j] = 0;
				cnttt--;
				For(i, 0, n - 1) if (ban[i]) assert(in[i] <= 2);
				work(j, w, fa[w], 1);
			}
		}
		int last = -1;
		for (int i = h[w]; ~i; i = ne[i]) {
			if (!is[i]) continue;
			int j = e[i];
			if (j == fa[w]) continue;
			if (last == -1) {
				last = j;
				continue;
			}
			assert(last != -1);
			find(j, w);
			ban[j] = 0;
			cnttt--;
			For(i, 0, n - 1) if (ban[i]) assert(in[i] <= 2);
			work(j, w, last, 1);
		} 
		assert(0);
	}
}
int main() {
	//assert(freopen("activity.in", "r", stdin));
	//assert(freopen("activity.out", "w", stdout));
	cin.tie(nullptr)->sync_with_stdio(false);
	cin >> n >> m;
	For(i, 1, m) cin >> u[i] >> v[i];
	Sub1::work();
	Sub2::solve(0);
	return 0;
} 
/*
5 4
0 1
0 2
0 3
0 4
*/

:::