#3701. 「一本通 3.7 例 1」欧拉回路 暂未评定

时间限制:1000 ms 内存限制:256 MiB 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: root

注意

出题人配置了 Special Judge 程序。本题答案可能不唯一或者题目有特殊要求,请注意审题。

题目描述

原题来自:UOJ #117

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

一共两个子任务:

  1. 这张图是无向图。( 分)

  2. 这张图是有向图。( 分)

输入格式

第一行一个整数 ,表示子任务编号。,如果 则表示处理无向图的情况,如果 则表示处理有向图的情况。

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

接下来 行中,第 行两个整数 ,表示第 条边(从 开始编号)。保证

  1. 如果 则表示 有一条无向边。

  2. 如果 则表示 有一条有向边。

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

输出格式

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

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

  1. 如果 ,输出 个整数 。令 ,那么 表示经过的第 条边的编号。如果 为正数表示从 走到 ,否则表示从 走到

  2. 如果 ,输出 个整数 。其中 表示经过的第 条边的编号。

样例

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

数据范围与提示