本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-12 21:19:39

注意到 $k \ge n+m$。

如果本题给定的图是欧拉图，那么可以在一次旅行中遍历一遍所有的边，也就意味着可以自由决定给定的所有边中保留哪些边。

此时，只需要 dfs 一遍找出一个生成树（此处默认 $s$ 为根），然后删除所有非树边，即可解决本题。

但是给定图并不保证是欧拉图。

但是题目并没有禁止我们多次遍历同一条边，也就是说可以添加不超过 $n$ 条额外的重边。

考虑对于要构建的那个生成树，对其从根开始递归处理，处理完当前节点的子树之后，若当前节点度数是奇数，那么向自己的父节点连一条边使得当前节点度数变为偶数。

但是根节点没有父节点怎么办？注意到若除了根节点以外的所有节点度数都为偶数了，那么根节点度数一定也是偶数，因为一条边对图的总度数贡献是 $2$，也就是说图的总度数为偶数。

无向图欧拉回路的一个简单的写法，可以考虑 set 维护所有出边，每搜索一个点，就将这条边从两个端点的出边列表删除，时间复杂度 $O(m \log m)$。

#include <bits\/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a\/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
#define islower(ch) (ch>='a'&&ch<='z')
#define isupper(ch) (ch>='A'&&ch<='Z')
#define isalpha(ch) (islower(ch)||isupper(ch))
template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x\/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
void ioopti(){
    ios::sync_with_stdio(0);
    cin.tie(0);
}
const int maxn=1e3+5;
int n,m,k,s;
vector<pii> g[maxn];
multiset<pii> g2[maxn]; 
bool ontree[maxn*maxn];
int deg[maxn];
bool vis[maxn];
void dfs1(int u,int _fa,int ine){
	vis[u]=1;
	for(auto& tmp:g[u]){
		if(!vis[tmp.fi]){
			ontree[tmp.se]=1;
			dfs1(tmp.fi,u,tmp.se);
		}
	}
	if(deg[u]&1)g2[u].insert(mkpr(_fa,ine)),g2[_fa].insert(mkpr(u,ine)),deg[u]++,deg[_fa]++;
}
stack<pii> ans;
int cur[maxn];
void dfs2(int u){
	while(!g2[u].empty()){
		auto tmp=*g2[u].begin();
		g2[u].erase(g2[u].begin());
		g2[tmp.fi].erase(g2[tmp.fi].find(mkpr(u,tmp.se)));
		dfs2(tmp.fi);
		ans.push(mkpr(tmp.se,ontree[tmp.se]));
	}
}
void solve(int id_of_test){
	read(n);
	read(m);
	read(k);
	read(s);
	FOR(i,1,m){
		int u,v;
		read(u);
		read(v);
		g[u].eb(mkpr(v,i));
		g[v].eb(mkpr(u,i));
		deg[u]++,deg[v]++;
	}
	FOR(u,1,n){
		for(auto& tmp:g[u])g2[u].insert(tmp);
	}
	dfs1(s,0,0);
	dfs2(s);
	printf("%d\n",int(ans.size()));
	while(!ans.empty()){
		printf("%d %d\n",ans.top().fi,ans.top().se);
		ans.pop(); 
	}
}
int main()
{
	int T;
	T=1;
	FOR(_,1,T){
		solve(_);
	}
	return 0;
}