1527：【例 1】欧拉回路

题目描述

有一天一位灵魂画师画了一张图，现在要你找出欧拉回路，即在图中找一个环使得每条边都在环上出现恰好一次。

一共两个子任务：

• 这张图是无向图。（50 分）
• 这张图是有向图。（50 分）

输入格式

第一行一个整数 $t$，表示子任务编号。$t \in \{1, 2\}$，如果 $t=1$ 则表示处理无向图的情况，如果 $t=2$ 则表示处理有向图的情况。

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

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

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

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

输出格式

如果不可以一笔画，输出一行 NO。

否则，输出一行 YES，接下来一行输出一组方案。

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

样例

样例输入 #1（无向图）

1
3 3
1 2
2 3
1 3

样例输出 #1

YES
1 2 -3

样例解释 #1

• $t=1$ 表示无向图。
• $n=3, m=3$。
• 边：
  1. $1-2$
  2. $2-3$
  3. $1-3$
• 该图存在欧拉回路（每个顶点的度数为偶数）。
• 输出方案：1 2 -3
  • 第一步走第 $1$ 条边，从 $1$ 到 $2$（因为 $p_1=1>0$，表示从 $v_1=1$ 到 $u_1=2$）。
  • 第二步走第 $2$ 条边，从 $2$ 到 $3$（$p_2=2>0$，从 $v_2=2$ 到 $u_2=3$）。
  • 第三步走第 $3$ 条边，从 $3$ 到 $1$（$p_3=-3<0$，表示从 $u_3=1$ 到 $v_3=3$？注意：对于无向边，$v_i$ 和 $u_i$ 没有方向，但输出中 $p_i$ 为正表示从 $v_i$ 到 $u_i$，为负表示从 $u_i$ 到 $v_i$）。这里 $-3$ 表示从 $u_3=1$ 到 $v_3=3$，即从 $1$ 到 $3$。但此时 $1$ 是起点吗？实际上回路是 $1 \to 2 \to 3 \to 1$，所以第三步是从 $3$ 到 $1$，符合。
• 回路为：$1 \to 2 \to 3 \to 1$。

样例输入 #2（有向图）

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

样例输出 #2

YES
4 1 3 5 2 6

样例解释 #2

• $t=2$ 表示有向图。
• $n=5, m=6$。
• 有向边：
  1. $2 \to 3$
  2. $2 \to 5$
  3. $3 \to 4$
  4. $1 \to 2$
  5. $4 \to 2$
  6. $5 \to 1$
• 该有向图存在欧拉回路（每个顶点的入度等于出度）。
• 输出方案：4 1 3 5 2 6
  • 表示依次经过边 $4, 1, 3, 5, 2, 6$。
  • 回路为：$1 \to 2 \to 3 \to 4 \to 2 \to 5 \to 1$。

数据范围

• $1 \le n \le 10^5$
• $0 \le m \le 2 \times 10^5$

时空限制

• 时间限制：1000 ms
• 内存限制：262144 KB

注意：本题要求输出欧拉回路的边的顺序。需要判断欧拉回路存在的条件：

• 无向图：所有顶点的度数均为偶数，且所有边属于同一个连通分量（忽略孤立点）。
• 有向图：所有顶点的入度等于出度，且所有边属于同一个弱连通分量（忽略孤立点）。

使用 Hierholzer 算法求欧拉回路，注意删除已访问的边（因为 $m$ 较大，可以用邻接表加删除标记或动态删除边）。对于无向图，每条边需要拆成两个方向，并注意输出时标记边的方向（正负号）。注意自环和重边的处理。