题目描述

一群研究员声称，友谊其实可以由食物偏好预测：每个人都有且仅有两种最喜欢的食物，两个人能够成为朋友，当且仅当他们的两种最爱食物中至少有一种相同。

他们选取了曼彻斯特一支著名乐团做实验。乐团中共有 $n$ 名音乐家，每名音乐家都选择了两种不同的最爱食物。

研究员发布了一份报告，列出了所有“可能成为朋友”的音乐家对，但没有公布每个人具体喜欢哪两种食物。

你觉得这份报告十分可疑。现在给定报告中的边集，请判断是否存在一种食物偏好分配，使得：

• 对于报告中列出的每一对音乐家，他们至少有一种共同最爱食物；
• 对于报告中没有列出的每一对音乐家，他们没有共同最爱食物；
• 每名音乐家恰好有两种不同的最爱食物。

如果存在，请构造任意一种方案。

食物种类只需要用整数编号表示，不同整数代表不同食物。

输入格式

第一行包含两个整数 $n,m$，表示音乐家数量和报告中的潜在朋友对数量。

接下来 $m$ 行，每行包含两个整数 $a_i,b_i$，表示音乐家 $a_i$ 和 $b_i$ 在报告中被认为可能成为朋友。

输出格式

如果不存在符合报告的食物偏好分配，输出：

No

否则，第一行输出：

Yes

接下来输出 $n$ 行，第 $i$ 行包含两个整数 $f_{i,0},f_{i,1}$，表示第 $i$ 名音乐家的两种最爱食物编号。

必须满足：

若存在多种方案，输出任意一种即可。

数据范围

• $1\le n\le 10^5$；
• $0\le m\le 10^5$；
• $1\le a_i,b_i\le n$；
• $a_i\ne b_i$；
• 所有无序点对 $(a_i,b_i)$ 两两不同；
• 输出的食物编号需满足 $-10^9\le f_{i,j}\le 10^9$。

样例 1

输入

7 6
4 2
6 4
2 7
2 6
7 6
3 1

输出

Yes
58 42
101 202
42 58
303 202
787788 50216
202 404
404 101

样例 2

输入

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

输出

No