Description

有一天一位灵魂画师画了一张图，现在要你找出欧拉回路，即在图中找一个环使得每条边都在环上出现恰好一次。 一共两个子任务： 1、这张图是无向图。（50分） 2、这张图是有向图。（50分）

Input Format

第一行一个整数 t，表示子任务编号。t∈{1,2}，如果 t=1则表示处理无向图的情况，如果 t=2则表示处理有向图的情况。 第二行两个整数 n,m，表示图的结点数和边数。 接下来 m 行中，第 i行两个整数 vi,ui，表示第 i 条边（从 1 开始编号）。保证 1≤vi,ui≤n1≤vi,ui≤n。 如果 t=1 则表示 vi到 ui有一条无向边。 如果 t=2则表示 vi 到 ui 有一条有向边。 图中可能有重边也可能有自环。

Output Format

如果不可以一笔画，输出一行 “NO”。 否则，输出一行 “YES”，接下来一行输出一组方案。 如果 t=1，输出 m个整数 p1,p2,…,pm。令 e=∣pi∣，那么 e 表示经过的第 i条边的编号。如果 pi为正数表示从 ve走到 ue，否则表示从 ue 走到 ve。 如果 t=2，输出个整数 p1,p2,…,pm。其中pi表示经过的第i条边的编号。

Sample

样例一 input

1 
3 3 
1 2 
2 3 
1 3

output

YES 
1  2  -3

样例二

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

output

YES 
4 1 3 5 2 6

Hint

1≤n≤105,0≤m≤2×1051≤n≤105,0≤m≤2×105 时间限制：1s1s 空间限制：256MB