不妨考虑树的情况，对于图只要取一棵生成树即可。
\(k\le 4n\) 是容易的，两个点分别 dfs 就是 \(\le 4n\) 次。
对于 \(k\le 3n\)，考虑一个做法：一个人去遍历整棵树，每次拓展新点时交换。不难证明正确性，次数 \(\le 3n\)。
考虑优化这个策略。注意到其中一个点一直在根，这非常浪费。事实上我们可以两个点同时递归两棵子树，每次同时走到一个新点然后交换。
但是这个优化在两棵子树大小差距过大时用处不大，考虑取重心，每个子树划分给某个人去遍历。假设分给两人的大小之和分别为 \(S_1\) 和 \(S_2\)，那么总次数就是 \(2\times(S_1+S_2)+\max(S_1,S_2)\)。
考虑从大往小考虑每棵子树，每次划分给较小的 \(S\)，可以证明 \(\max S\le \dfrac{2}{3}n\)，总次数 \(\le\dfrac{8}{3} n\)。
code
#include <bits/stdc++.h>
#define ALL(x) begin(x), end(x)
using namespace std;
void file() {
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
}
using ll = long long;
const int kL = 5e5 + 5;
int n, m;
array<int, kL> siz;
array<bool, kL> vis;
array<vector<int>, kL> g;
string A = "Ran", B = "Chen";
struct DSU {
array<int, kL> fa;
DSU() { iota(ALL(fa), 0); }
int find(int x) {
return (fa[x] == x) ? x : (fa[x] = find(fa[x]));
}
void merge(int x, int y) { fa[find(x)] = find(y); }
}dsu;
int findrt(int x, int Fa) {
int mx = 0, rt = 0; siz[x] = 1;
for(int to : g[x]) {
if(to == Fa) continue;
if(int tmp = findrt(to, x))
rt = tmp;
siz[x] += siz[to];
mx = max(mx, siz[to]);
}
mx = max(mx, n - siz[x]);
return (mx * 2 <= n) ? x : rt;
}
void dfs(int x, int Fa) {
if(Fa) g[x].erase(find(ALL(g[x]), Fa));
for(int to : g[x]) dfs(to, x);
}
vector<pair<string, int>> ans;
void push(int x, vector<int>& buc) {
buc.push_back(x);
for(int to : g[x]) {
push(to, buc);
buc.push_back(x);
}
}
vector<int> vx, vy;
void solve(int x, int Fa) {
if(g[x].empty()) return ;
sort(ALL(g[x]), [&](int a, int b) { return siz[a] > siz[b]; });
for(int to : g[x]) {
vector<int> buc;
push(to, buc);
buc.push_back(x);
if(vx.size() < vy.size()) {
for(int i : buc) vx.push_back(i);
}else {
for(int i : buc) vy.push_back(i);
}
}
}
void getans() {
int i, j;
for(i = j = 0; (i < vx.size()) && (j < vy.size()); ) {
int a = vx[i], b = vy[j];
if(vis[a]) { ans.emplace_back(A, a); i++; }
if(vis[b]) { ans.emplace_back(B, b); j++; }
if(!vis[a] && !vis[b]) {
i++, j++, vis[a] = vis[b] = 1;
ans.emplace_back(A, a);
ans.emplace_back(B, b);
ans.emplace_back("Swap", -1), swap(A, B);
}
}
for(; i < vx.size(); i++) {
int p = vx[i];
if(vis[p]) ans.emplace_back(A, p);
else {
vis[p] = 1;
ans.emplace_back(A, p);
ans.emplace_back("Swap", -1), swap(A, B);
}
}
for(; j < vy.size(); j++) {
int p = vy[j];
if(vis[p]) ans.emplace_back(B, p);
else {
vis[p] = 1;
ans.emplace_back(B, p);
ans.emplace_back("Swap", -1), swap(A, B);
}
}
}
int main() {
// file();
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
for(int i = 1, u, v; i <= m; i++) {
cin >> u >> v;
if(dsu.find(u) != dsu.find(v)) {
dsu.merge(u, v);
g[u].push_back(v);
g[v].push_back(u);
}
}
ans.reserve(3 * n);
vx.reserve(2 * n);
vy.reserve(2 * n);
int root = findrt(1, 0);
assert(findrt(root, 0) == root);
dfs(root, 0), solve(root, 0), getans();
cout << root << " ";
cout << ans.size() << "\n";
for(auto k : ans) {
if(~k.second) cout << k.first << " " << k.second << "\n";
else cout << k.first << "\n";
}
return 0;
}