멘토링 시스템

넥슨의 한 게임에는 신규 유저의 게임 적응을 돕기 위한 멘토링 시스템이 있다.

이 멘토링 시스템에는 게임을 오래 플레이한 멘토가 $N$ 명 등록되어있고, 새로 게임에 가입한 멘티 $N$ 명이 등록되어 있어, 이들을 1:1 매칭시킨다. 편의상, 각 멘토는 $1$부터 $N$까지 번호가 매겨져 있고, 각 멘티 또한 $1$부터 $N$까지 번호가 매겨져 있다.

어떤 멘토와 어떤 멘티를 아무 이유 없이 매칭시켜주면 멘토링 시스템의 질이 떨어질 수 있기 때문에, 유저들의 접속 시간대, 플레이 스타일, 직업군 등 다양한 요소를 고려하여 멘토링이 가능한 멘토와 멘티 쌍이 결정되었다.

예를 들어, $N = 3$인 상황을 보자.

• 멘토 $1$이 멘티 $3$과 멘토링이 가능하고,
• 멘토 $2$가 멘티 $1$과 멘토링이 가능하고,
• 멘토 $2$가 멘티 $2$와 멘토링이 가능하고,
• 멘토 $3$이 멘티 $1$과 멘토링이 가능하고,
• 멘토 $3$이 멘티 $2$와 멘토링이 가능하다고 하자.

멘토 $1$을 멘티 $3$과, 멘토 $2$를 멘티 $1$과, 멘토 $3$을 멘티 $2$와 매칭해줄 수 있다.

다른 방법 또한 가능한데, 멘토 $1$을 멘티 $3$과, 멘토 $2$를 멘티 $2$와, 멘토 $3$을 멘티 $1$과 매칭해줄 수도 있다. 즉, 1:1 매칭은 가능하지만 그 방법이 유일하지 않다.

$N = 3$인 다른 상황을 보자.

• 멘토 $1$이 멘티 $2$와 멘토링이 가능하고,
• 멘토 $2$가 멘티 $1$과 멘토링이 가능하고,
• 멘토 $2$가 멘티 $2$와 멘토링이 가능하고,
• 멘토 $2$가 멘티 $3$과 멘토링이 가능하고,
• 멘토 $3$이 멘티 $2$와 멘토링이 가능하다고 하자.

이 경우, 멘토 $1$은 멘티 $2$와만 멘토링이 가능하고, 멘토 $3$ 또한 멘티 $2$와만 멘토링이 가능하다. 즉, 1:1 매칭이 불가능하다.

마지막으로, $N = 3$인 다른 상황을 보자.

• 멘토 $1$이 멘티 $2$와 멘토링이 가능하고,
• 멘토 $2$가 멘티 $2$와 멘토링이 가능하고,
• 멘토 $2$가 멘티 $3$과 멘토링이 가능하고,
• 멘토 $3$이 멘티 $1$과 멘토링이 가능하고,
• 멘토 $3$이 멘티 $3$과 멘토링이 가능하다고 하자.

멘토 $1$은 멘티 $2$와, 멘토 $2$는 멘티 $3$과, 멘토 $3$은 멘티 $1$과 매칭해줄 수 있다. 다른 방법으로는 매칭이 불가능하다. 즉, 1:1 매칭이 가능하며 그 방법이 유일하다.

멘토와 멘티의 수 $N$과 멘토링이 가능한 멘토와 멘티 쌍이 주어졌을 때, 이들을 1:1 매칭시키는 것이 가능하며, 그 방법이 유일한지 구하는 프로그램을 작성하시오.

입력 형식

첫 줄에 멘토와 멘티의 수를 나타내는 정수 $N$과 멘토링이 가능한 멘토와 멘티 쌍의 수를 나타내는 정수 $M$이 공백으로 구분되어 주어진다. ($1 \le N \le M \le 1\,000\,000$)

이어지는 $M$ 개의 줄에 멘토의 번호를 나타내는 정수 $i$와 멘티의 번호를 나타내는 정수 $j$가 공백으로 구분되어 주어진다. ($1 \le i, j \le N$)

이는 멘토 $i$와 멘티 $j$가 멘토링이 가능하다는 것을 의미한다. 같은 $(i, j)$ 쌍이 여러 번 주어지지 않는다.

출력 형식

첫 줄에 $N$ 명의 멘토와 $N$ 명의 멘티를 1:1 매칭시키는 것이 가능하며, 그 방법이 유일하다면 YES를 출력하고, 그렇지 않다면 NO를 출력한다.

만약 답이 YES라면, 이어지는 $N$ 줄의 $i$ 번째 줄에 멘토 $i$와 매칭될 멘티의 번호 $j$를 출력한다.

예제 1

3 5
1 2
2 2
2 3
3 1
3 3

YES
2
3
1

예제 2

3 5
1 3
2 1
2 2
3 1
3 2

NO

예제 3

3 5
1 2
2 1
2 2
2 3
3 2

NO

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설