题意

给出一张 \( n \) 个点，\( m \) 条边的无向连通图，图中无自环、重边，初始位置为 \( s \)，每次沿边移动，移动后可以选择是否删除当前这条边。未删除的边可以多次移动，求构造 \( k \) 步移动内未删除边组成树的移动方案。

对于 \( 100 % \) 的数据，\( n \leq 10^3 \)，\( n - 1 \leq m \leq \frac{n(n - 1)}{2} \)，\( k \leq m + n \)。保证有解。

Subtask 1、2 和 4

考虑先钦定一棵生成树，在树上移动并且删除剩下不在生成树上的边。容易发现遍历整棵树时，树上每条边最多经过 \( 2 \) 次，而对于每条多余的边，一去一回删除也最多经过 \( 2 \) 次，总移动步数最多为 \( 2m \) 次，又有 \( m \leq \frac{n(n - 1)}{2} \)，则移动步数严格小于 \( n^2 \)，可通过 Subtask 1、2 和 4。

Subtask 3

\( m = n \)，基环树。判断出需要删掉的边，移动到此位置并删掉即可。移动步数严格小于 \( n \) 步。

其实用上面所述生成树的写法也可以。

Subtask 5

前面的 Subtask 其实和正解没有特别强的相关性。注意到如果这张图是一张欧拉图，那么肯定有一个显然的解法：还是钦定一棵生成树，在跑欧拉路径的时候判断若为树边则保留，否则删去。这样的最大移动步数为 \( m \) 次。

于是考虑怎么把一张普通的图变成一张欧拉图。往图中加边，在 dfs 遍历生成树上节点的时候，判断该点度数是否为偶。若为奇则向父节点连边。可以证明最后会形成一个欧拉图。

对于增加的边，由于原先向父节点的连边为树边，所以保证这条边不会被删除。根节点不用向上连边，最多增加边数为 \( n - 1 \)，总移动次数严格小于 \( n + m \)。

实现细节上要注意在 dfs 遍历的同时不要加边。这是未定义行为。可能会导致 RE 或 WA。

如何证明“最后一定会形成一个欧拉图”？

简单意会即可。欧拉图的总度数必为偶数，保证了根节点以下的度数均为偶，那么根节点的度数也必然为偶。

代码

dfs 的时候可以直接生成树，我也不知道当时为什么写了个并查集。

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stack>
#include <cstring>
#include <cstdio>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using pii = pair<int, int>;
#define FILENAME "path"
const int N = 3e6 + 10;
const i64 P = 1e9 + 7;
struct node {
	int v, tag, ID;
	node() : v(0), tag(0), ID(0) {}
	node(int v, int tag, int ID) : v(v), tag(tag), ID(ID) {}
};
int n, m, k, s;
int deg[N], fa[N], etag[N]; // etag：每条边对应的 tag
vector <node> G[N];
int rel[N], vis[N]; // rel：新建边对应的旧边编号
int Find(int x) {
	return (x == fa[x]) ? x : fa[x] = Find(fa[x]);
}
// 构造欧拉图
vector <node> V[N];
void dfs1(int u, int f, int fid) {
	for(auto [v, tag, ID] : G[u]) {
		if(v == f) continue;
		if(tag == 1) dfs1(v, u, ID);
	}
	if((deg[u] & 1) && u != s) {
		m++;
		G[u].emplace_back(node(f, 2, m));
		V[f].emplace_back(node(u, 2, m)); // 不要在遍历时加边
		rel[m] = fid, etag[m] = 2, deg[u]++, deg[f]++;
	}
	return void();
}
// 无向图欧拉路径
vector <pii> ans;
int now[N];
void dfs2(int u, int fid) {
	if(vis[fid]) return void();
	vis[fid] = 1;
	for(; now[u] < G[u].size();) {
		auto [v, tag, ID] = G[u][now[u]++];
		dfs2(v, ID);
	}
	if(fid) ans.emplace_back(make_pair(fid, etag[fid]));
	return void();
}
void solve() {
	cin >> n >> m >> k >> s;
	int rm = m;
	for(int i = 1; i <= n; i++) fa[i] = i;
	for(int i = 1; i <= m; i++)  {
		int u, v; cin >> u >> v;
		int uu = Find(u), vv = Find(v);
		if(uu == vv) {
			etag[i] = 0;
			G[u].emplace_back(node(v, 0, i)); G[v].emplace_back(node(u, 0, i));
		} else {
			etag[i] = 1;
			G[u].emplace_back(node(v, 1, i)); G[v].emplace_back(node(u, 1, i));
			fa[uu] = vv;
		}
		deg[u]++, deg[v]++;
	}
	dfs1(s, s, 0);
	for(int i = 1; i <= n; i++) {
		for(auto k : V[i]) G[i].push_back(k);
	}
	dfs2(s, 0);
	reverse(ans.begin(), ans.end());
	cout << ans.size() << '\n';
	for(auto [i, j] : ans) cout << (i > rm ? rel[i] : i) << ' ' << (j ? 1 : 0) << '\n';
	return void();
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
#ifdef FILENAME
	freopen(FILENAME ".in", "r", stdin);
	freopen(FILENAME ".out", "w", stdout);
#endif
	solve();
	return 0;
}