题目描述

学校里有 N 个人，他们之间有 M 对互相认识的人。你可以把每一对“认识关系”定向成单向“喜欢关系”：若输出 A B，表示 A 喜欢 B。

要求是：对学校中的每个人，都必须满足：

• 他喜欢的人数 与 喜欢他的人数 之差的绝对值不超过 1。

也就是说，把每个人看成图中的一个点，把“喜欢”看成有向边，那么每个点的出度和入度之差的绝对值都不能超过 1。

请判断是否存在这样的定向方案；如果存在，输出任意一组可行方案。

输入格式

第一行输入两个整数 N, M，分别表示人数和认识关系数。

接下来 M 行，每行两个整数 P1, P2，表示 P1 与 P2 互相认识。

保证每对认识关系在输入中恰好出现一次。

输出格式

• 如果不存在可行方案，输出一行 No；
• 否则，第一行输出 Yes，接下来 M 行，每行输出两个整数 P1 P2，表示将对应认识关系定向为 P1 -> P2。

如果可行方案不唯一，输出任意一个即可。

数据范围

• 1 <= N <= 1000
• 1 <= M <= 100000
• 在 30% 的测试中，N,M <= 20

样例

输入

5 7
1 2
1 3
4 1
1 5
3 2
4 5
3 5

输出

Yes
1 2
3 1
4 1
1 5
2 3
5 4
3 5

样例说明

共有 5 名学生、7 对认识关系。定向后，除 5 号同学比“喜欢别人”少 1、3 号同学比“被喜欢”少 1 以外，其余每个人的入度和出度完全相等，因此满足题意。