1184

1184. 欧拉回路

题目

给定一张图，请你找出欧拉回路，即在图中找一个环使得每条边都在环上出现恰好一次。

输入格式

第一行包含一个整数 $t$，$t \in \lbrace 1,2 \rbrace$，如果 $t = 1$，表示所给图为 无向 图，如果 $t = 2$，表示所给图为 有向 图。

第二行包含两个整数 $n,m$，表示图的结点数和边数。

接下来 $m$ 行中，第 $i$ 行两个整数 $v_i,u_i$，表示第 $i$ 条边（从 $1$ 开始编号）。

• 如果 $t = 1$ 则表示 $v_i$ 到 $u_i$ 有一条无向边。
• 如果 $t = 2$ 则表示 $v_i$ 到 $u_i$ 有一条有向边。

图中可能有重边也可能有自环。

点的编号从 $1$ 到 $n$。

输出格式

如果无法一笔画出欧拉回路，则输出一行：NO。

否则，输出一行：YES，接下来一行输出 任意一组 合法方案即可。

• 如果 $t=1$，输出 $m$ 个整数 $p_1,p_2,…,p_m$。令 $e = |p_i|$，那么 $e$ 表示经过的第 $i$ 条边的编号。如果 $p_i$ 为正数表示从 $v_e$ 走到 $u_e$，否则表示从 $u_e$ 走到 $v_e$。
• 如果 $t=2$，输出 $m$ 个整数 $p_1,p_2,…,p_m$。其中 $p_i$ 表示经过的第 $i$ 条边的编号。

数据范围

$1 \le n \le 10^5$,

$0 \le m \le 2 \times 10^5$

输入样例1：

1
3 3
1 2
2 3
1 3

输出样例1：

YES
1 2 -3

输入样例2：

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

输出样例2：

YES
4 1 3 5 2 6

题解