19311번 - I've Got Friends 스페셜 저지다국어

British scientists have found out that friendship is very predictable. They claim that two people can become friends if and only if they have at least one common favorite type of food among two favorite types of food of both.

A famous orchestra from Manchester was chosen for a scientific experiment. Each musician was asked to choose exactly two distinct types of food they like the most. 

In the initial report, the scientists have published the full list of pairs of musicians who can become friends according to their theory. The list of favorite types of food hasn't been published, though.

This looks suspicious to you, and you don't really trust this kind of scientific research. You'd like to check if this list of potential friendships is at all possible for some list of food preferences.

The first line of the input contains two integers $n$ and $m$ ($1 \le n \le 10^5$; $0 \le m \le 10^5$) --- the number of musicians in the experimental group and the number of potential pairs of friends, respectively. The musicians are numbered from 1 to $n$.

Each of the next $m$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$; $a_i \ne b_i$) --- the numbers of musicians who can potentially be friends according to the scientific report.

All unordered pairs $(a_i, b_i)$ are distinct.

If it's impossible to form a list of favorite types of food which doesn't contradict the report, output "No".

Otherwise, output "Yes" followed by $n$ pairs of integers $f_{i, 0}$ and $f_{i, 1}$ ($-10^9 \le f_{i, j} \le 10^9$; $f_{i, 0} \ne f_{i, 1}$) --- identifiers of favorite types of food of the $i$-th musician. Different integers correspond to different types of food.