题目描述
原题来自：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 图论 欧拉回路