커플 깨기

정보를 좋아하는 고등학생 민솔이는 커플이 늘어나는 상황이 마음에 들지 않는다. 민솔이는 이 문제를 해결하기 위해 정보에 매우 능한 승원이에게 도움을 요청했다.

승원이는 학교의 각 학생을 그래프의 정점으로 보고, A가 B를 좋아한다는 관계를 A -> B 방향의 간선으로 생각했다. 모든 학생에 대해 그 학생을 좋아하는 사람의 수와 그 학생이 좋아하는 사람의 수의 차이가 1 이하라면 민솔이가 원하는 상태를 만들 수 있다. 즉, 모든 정점 v에 대해 다음 조건을 만족해야 한다.

|indegree(v) - outdegree(v)| <= 1

승원이는 학교 안에서 서로 알고 있는 학생 쌍을 모두 알고 있다. 서로 알고 있는 두 학생 A, B에 대해서는 A가 B를 좋아하게 만들 수도 있고, 반대로 B가 A를 좋아하게 만들 수도 있다. 다시 말해, 주어진 무방향 그래프의 각 간선에 대해 두 방향 중 하나를 선택해야 한다.

승원이는 관계 정보만 남기고 떠나 버렸다. 민솔이를 도와 모든 간선의 방향을 정해 위 조건을 만족하는 방향 그래프를 만들어 보자.

첫째 줄에 정수 N과 M이 공백으로 구분되어 주어진다. N은 학생의 수, M은 서로 알고 있는 학생 쌍의 수이다.

1 <= N <= 1000, 1 <= M <= 100000

다음 M개의 줄에는 정수 A, B가 공백으로 구분되어 주어진다. 이는 A번 학생과 B번 학생이 서로 알고 있음을 뜻한다.

같은 학생 쌍은 두 번 이상 주어지지 않는다.

조건을 만족하도록 모든 간선의 방향을 정할 수 있다면 첫째 줄에 Yes를 출력한다. 그다음 M개의 줄에는 각 간선의 방향을 나타내는 두 정수 A, B를 출력한다. 이는 A가 B를 좋아하도록, 즉 간선의 방향을 A -> B로 정했다는 뜻이다.

가능한 방법이 여러 가지라면 그중 아무 방법이나 출력해도 된다.

조건을 만족하는 방향 배정이 불가능하다면 첫째 줄에 No를 출력한다.

공개 테스트의 한 출력처럼 방향을 정하면 1, 2, 4번 학생은 들어오는 간선 수와 나가는 간선 수가 같아진다. 3번 학생은 나가는 간선이 들어오는 간선보다 1개 많고, 5번 학생은 들어오는 간선이 나가는 간선보다 1개 많아 조건을 만족한다.