You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

求有向图字典序最小的欧拉路径。

输入格式

第一行两个整数 $n,m$ 表示有向图的点数和边数。

接下来 $m$ 行每行两个整数 $u,v$ 表示存在一条 $u\to v$ 的有向边。

输出格式

如果不存在欧拉路径，输出一行 No。

否则输出一行 $m+1$ 个数字，表示字典序最小的欧拉路径。

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

1 2 1 3 3 4 2

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

1 2 3 4 3 5

4 3
1 2
1 3
1 4

No

提示

对于 $50\%$ 的数据，$n,m\leq 10^3$。

对于 $100\%$ 的数据，$1\leq u,v\leq n\leq 10^5$，$m\leq 2\times 10^5$。

保证将有向边视为无向边后图连通。

本题的数据生成器：

#include<bits/stdc++.h>
#include<windows.h>
using namespace std;
typedef unsigned long long ull;
#define N 100005
#define For(i,x,y)for(i=x;i<=(y);i++)
bool bo[N];
queue<int>p,q;
ull R=GetTickCount();
int deg[N][2],dep[N],fa[N];
inline int Rand(int _,int __)
{
	R^=R<<13;
	R^=R>>7;
	R^=R<<17;
	return R%(__-_+1)+_;
}
int find(int p)
{
	if(p!=fa[p])fa[p]=find(fa[p]);
	return fa[p];
}
inline void unite(int p,int q)
{
	p=find(p),q=find(q);
	if(p==q)return;
	if(dep[p]<dep[q])fa[p]=q;
	else fa[q]=p;
	if(dep[p]==dep[q])dep[p]++;
}
int main()
{
	freopen("P7771.in","w",stdout);
	int n=Rand(1,100000),m=Rand(190000,200000),i,u,v;
	cout<<n<<' '<<m;
	For(i,1,n)fa[i]=i;
	For(i,1,m>>1)
	{
		u=Rand(1,n),v=Rand(1,n);
		cout<<endl<<u<<' '<<v;
		unite(u,v);
		deg[u][0]++;
		deg[v][1]++;
	}
	m-=m>>1;
	For(i,1,n)
	if(deg[i][0]<deg[i][1])p.push(i);
	else if(deg[i][0]>deg[i][1])q.push(i);
	while(m)
	{
		if(p.empty()||q.empty())break;
		u=p.front();
		v=q.front();
		p.pop();
		q.pop();
		unite(u,v);
		cout<<endl<<u<<' '<<v;
		deg[u][0]++;
		deg[v][1]++;
		if(deg[u][0]<deg[u][1])p.push(u);
		if(deg[v][0]>deg[v][1])q.push(v);
		m--;
	}
	For(i,1,n-1)
	if(find(i)!=find(n))
	{
		cout<<endl<<n<<' '<<i<<endl<<i<<' '<<n;
		m-=2;
		unite(n,i);
	}
	if(m<2)
	while(1);
	while(m>Rand(0,1))
	{
		u=Rand(1,n);
		cout<<endl<<u<<' '<<u;
		m--;
	}
	if(m)cout<<endl<<Rand(1,n)<<' '<<Rand(1,n);
	return 0;
}