Like
Like
Have you noticed, that if we remove the letter 'k' from the word "like" and make all cyclic rotations, one of them will be "eli"? This could become a great task, however in this one you will deal neither with words, nor with cyclic rotations.
Elly is facing a big problem. Recently she was accused (not without a reason) that all boys in her class like her (while not paying any attention to the other girls), and she, on the other hand, is not paying any attention to the boys. This accusation was made mostly because some of her schoolmates were jealous that she is much more liked than she likes the others. Elly, on the other hand, is against relationships - that is also the reason why she ignores the boys in her class. Something more - she would be happy if there are as few as possible couples around her.
In order to avoid future conflicts, she decided to make sure that for every person in the school the following holds: the number of people he likes differs from the number of people that like him by no more than 1. Put in a more human language, if we imagine that each person is a node in a graph and the fact that A likes B as directed edge from A to B in the graph, then she wants the number of incoming edges to differ from the number of outgoing edges by no more than 1.
She has decided to use her charm and diplomacy (also known as deceit and manipulation) in order to achieve this. Elleonora knows all pairs of people in the school that know each-other (which we can assume is an undirected edge in the graph). She can make any pair of acquaintances change their relationship, so that one of them starts liking the other or viceversa, but not both at the same time (don't forget that she is against having couples in the school). She wants to execute her evil plan by "directing" all edges in the graph - i.e. each acquaintanceship to become a one-way crush.
You decide to check if she can do that - and if she can to show one of the possible directions of the edges.
Input
On the first line will be given two space separated integers n (1 ≤ n ≤ 1000) and m (1 ≤ n ≤ 105
) - the number of people in the school and the number of acquaintances, respectively. On each of the following m lines will be given a pair of space separated numbers p1
and p2
(1 ≤ p1
, p2
≤ n), meaning that the students p1
and p2
know each-other. Each acquaintance will be given exactly once in the input. All numbers in the input will be positive integers.
Output
On the first line print "Yes" if such direction of the edges is possible, or "No" otherwise (quotes for clarity only). If the answer is "Yes" on each of the next m lines print a pair of space separated integers p1
p2
, meaning that p1
likes p2
.
If there exist more than one such way to direct the edges, print any of them.
Explanation
There are 5 students and 7 acquaintances between them. After directing the edges in the graph, each student is liked by and likes equal amount of people, except 5, who is liked by one more person, and 3, who likes one more person.
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