1671: 欧拉回路

题目描述


原题来自:UOJ #117
有一天一位灵魂画师画了一张图,现在要你找出欧拉回路,即在图中找一个环使得每条边都在环上出现恰好一次。
一共两个子任务:
这张图是无向图。(
50
50 分)
这张图是有向图。(
50
50 分)

输入


第一行一个整数
t
t,表示子任务编号。
t \in \{1, 2\}
t∈{1,2},如果
t = 1
t=1 则表示处理无向图的情况,如果
t = 2
t=2 则表示处理有向图的情况。
第二行两个整数
n, m
n,m,表示图的结点数和边数。
接下来
m
m 行中,第
i
i 行两个整数
v_i, u_i
vi
,ui
,表示第
i
i 条边(从
1
1 开始编号)。保证
1 \leq v_i, u_i \leq n
1≤vi
,ui
≤n。
如果
t = 1
t=1 则表示
v_i
vi

u_i
u
i
有一条无向边。
如果
t = 2
t=2 则表示
v_i
vi

u_i
ui
有一条有向边。
图中可能有重边也可能有自环

输出


如果不可以一笔画,输出一行 NO。
否则,输出一行 YES,接下来一行输出一组方案。
如果
t = 1
t=1,输出
m
m 个整数
p_1, p_2, \dots, p_m
p1
,p2
,…,pm
。令
e = \lvert p_i \rvert
e=∣pi
∣,那么
e
e 表示经过的第
i
i 条边的编号。如果
p_i
pi
为正数表示从
v_e
ve
走到
u_e
ue
,否则表示从
u_e
ue
走到
v_e
ve

如果
t = 2
t=2,输出
m
m 个整数
p_1, p_2, \dots, p_m
p1
,p2
,…,pm
。其中
p_i
p
i
表示经过的第
i
i 条边的编号。

样例输入


【样例输入1】
1
3 3
1 2
2 3
1 3
【样例输入2】
2
5 6
2 3
2 5
3 4
1 2
4 2
5 1

样例输出


【样例输出1】
YES
1 2 -3
【样例输出2】
YES
4 1 3 5 2 6

提示


数据范围与提示
1 \leq n \leq 10^5, 0 \leq m \leq 2 \times 10^5
1≤n≤105,0≤m≤2×105

来源/分类


ybttg 图论 欧拉回路

请先 登录 后评论
  • 0 关注
  • 0 收藏,481 浏览
  • 轩爸 提出于 2019-08-02 22:18

相似问题