4045 合作

题面

内容

现在 Y 国在战场有 $n$ 个阵地，这些阵地由 $m$ 条隧道连接，第 $i$ 条隧道连接着编号分别为 $u_i,v_i$ 的阵地。Y 国在每条隧道中都恰好安排了一名士兵驻守。

Y 国研发了新型的秘密武器，这种武器需要恰好两名士兵来合作使用。现在，士兵们要分别前往某个阵地领取这些武器。

为了保持警戒，士兵们不能离开其驻守的隧道太远，所以士兵只能去到其驻守的隧道所连接的两个阵地中的其中一个。为了能恰好分配新型武器，要求对于每个阵地而言，到达它的士兵数量必须是偶数。每个士兵必须选择一个阵地前往。

你现在需要帮助 Y 国决定每个士兵要前往哪个阵地，使得新型武器能被恰好分配。如果无论如何都不能使得每个阵地上士兵数量为偶数，那么报告无解。

输入

第一行两个整数 $n,m$。

接下来 $m$ 行每行两个整数表示 $u_i,v_i$。

输出

假如无解，输出一行 NO。

否则输出一行 YES，接下来输出 $m$ 行每行一个 $u_i,v_i$ 之中的整数，表示第 $i$ 条隧道的士兵被安排到哪个阵地。你需要保证每个数都出现偶数次。(请不要输出多余的空格和换行，否则可能被判定为格式错误)

样例1

输入

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

输出

YES
5
5
2
4
4
2

样例2

输入

2 1
1 2

输出

NO

提示

对于样例2：只有一个士兵，显然不可能有合法方案。

本次下发文件中含有 chk.cpp 和 chk.exe 作为参考评分器，请注意，参考评分器和实际评测用的评分器不完全相同。你可以使用命令 chk.exe <input-file> <output-file> <anything> 来使用评分器，其中 <input-file> 为你的输入文件的路径，<output-file> 为你的输出文件的路径，<anything> 为一个任意的文件的路径。示例：chk.exe cooperater.in cooperater.out cooperater.out。

思路

题意：对于一个无向图，让你给定每条边方向，使得每个节点的入度为偶数。

首先，士兵人数一定要是偶数，否则不管怎么分配也一定无法分全。

也就是边的数量为偶数。

对于一颗树，叶子节点是绝对不能去的，因为这样不可能是偶数。那就从叶子节点开始，士兵向上走，如果当前点士兵数是奇数，那就让它上面的边的士兵向下走到这个点，否则就向上走。

这样就可以维护所有非根的点的士兵数都为偶数，由于士兵总数为偶数，那么根节点最后也一定是偶数。

但是这样一张无向图不一定是树，所以我们可以建一颗 DFS 树，无向图中， DFS 生成树仅存在树边和回边，所以对于每个回边，我们让它回到深度更大的点，剩下的就和树上是一模一样的了。