시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 76 21 15 24.590%

문제

정보를 좋아하는 고등학생 민솔이는 커플을 싫어한다. 그런데 요즘 주변에서 커플이 많이 출몰하는 것을 본 민솔이는 마음이 많이 심란하다. 민솔이는 이 문제를 해결하기 위해 정보를 매우 잘하는 '갓' 승원이를 찾아갔다.

승원이는 잠시 생각해 본 후, 학교의 모든 사람에 대해 그 사람이 좋아하는 사람의 수와 그 사람을 좋아하는 사람의 수의 차가 1 이하가 된다면 모든 커플을 깨트릴 수 있다는 것을 알아내었다. 다시 말해, 각 사람을 그래프의 노드로 보고, 'A가 B를 좋아한다'라는 것을 A에서 B를 가리키는 방향성 간선(즉, A -> B)으로 생각했을 때, 각 노드에 대해 |(그 노드로 들어오는 간선의 수) - (그 노드에서 나가는 간선의 수)|가 1 이하가 되면 된다는 것이다.

승원이는 '갓'이기 때문에, 학교 내에서 서로 알고 있는 학생의 쌍의 정보에 대해 모두 알고 있다. 그리고 승원이는 임의의 서로 아는 두 학생 A, B에 대해, A가 B를 좋아하거나, B가 A를 좋아하게 만들 수 있다. 즉, 어떤 무방향성 그래프가 주어지면, 승원이는 어떤 (s, e)를 잇는 간선에 대해 s -> e 또는 e -> s의 방향성 간선을 만들 수 있다는 것이다.

민솔이가 위의 조건을 만족하는 간선 방향 조합을 어떻게 생성하면 되는지 물어보려는 순간, 승원이는 "난 Persistent Segment Tree를 짜러 가야 해서... 그럼 이만!" 이라는 이상한 말과 함께 학생들 간의 관계 정보만을 남기고 떠나가버렸다.

어찌할 지 몰라 잉잉 울고 있는 민솔이를 도와 커플을 깨트릴 수 있는 간선 방향 조합을 찾아 승원이에게 알려주자!

입력

첫째 줄에는 공백으로 구분된 정수 N과 M이 주어진다(1 ≤ N ≤ 1000, 1 ≤ M ≤ 100000). N은 학생의 수, M은 두 학생이 서로 아는 관계의 수를 나타낸다.

다음 M개의 줄에는 각 줄별로 공백으로 구분된 정수 A, B가 주어진다(1 ≤ A, B ≤ N). 이는 A번 학생과 B번 학생이 서로 알고 있음을 나타낸다. (A, B)의 쌍은 중복해서 들어오지 않는다.

출력

만약 문제의 조건을 만족하도록 각 간선의 방향을 설정하는 것이 가능하다면 첫 번째 줄에 "Yes"를 출력하고, (따옴표 제외) 이후의 M개 줄에 각각 정수 A, B를 출력한다. 이는 A가 B를 좋아한다(즉, A -> B로 방향을 설정했다)라는 의미이다. 조건을 만족하도록 간선의 방향을 설정하는 방법이 여러 가지라면 그 중 아무 방법이나 출력하면 된다.

만약 문제의 조건을 만족하도록 간선의 방향을 설정하는 것이 불가능하면 첫 번째 줄에 "No"를 출력한다. (따옴표 제외)

예제 입력

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개의 서로 아는 관계가 있다. 예제 출력과 같이 간선 방향을 설정하고 나면, 1, 2, 4번 학생은 자신이 좋아하는 학생 수와 자신을 좋아하는 학생 수가 같으며, 3번 학생은 자신이 좋아하는 학생 수가 자신을 좋아하는 학생 수보다 1 많으며, 5번 학생은 자신을 좋아하는 학생 수가 자신이 좋아하는 학생 수보다 1 많게 되어 문제의 조건을 만족한다.

출처

Olympiad > International Tournament in Informatics > Shumen 2010 A1번

  • 문제를 번역한 사람: kdh9949