题目描述

原题来自：[UOJ #17]

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

一共两个子任务：

$\red{1}$. 这张图是无向图。（$\red{50}$ 分）

$\red{2}$. 这张图是有向图。（$\red{50}$ 分）

输入格式

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

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

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

$\red{1.}$ 如果$\red{ t=1}$ 则表示 $\red{v_i }$到 $\red{u_i​ }$有一条无向边。

$\red{2. }$如果$\red{ t=2}$ 则表示$\red{ v_i​ }$到 $\red{u_i }$有一条有向边。

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

输出格式

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

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

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

$\red{2}$. 如果 $\red{t=2}$，输出$\red{ m}$ 个整数 $\red{p_1, p_2, \dots, p_m}$。其中$\red{ p_i }$表示经过的第$\red{ i }$条边的编号。

样例

输入样例 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

提示

$\red{1 \leq n \leq 10^5, 0 \leq m \leq 2 \times 10^5}$