30411번 - 그래프 게임 스페셜 저지

문제

춘배는 그래프 게임을 하고 있다. 그래프 게임은 초기에 정점이 $N$개이고 간선은 0ドル$개인 그래프에 방향이 없는 간선을 하나씩 추가하며 진행된다. 정점 번호는 1ドル$부터 $N$까지이다.

간선을 추가할 때 다음 조건을 만족해야 한다.

• 이미 그래프에 정점 $u$와 정점 $v$를 연결하는 간선이 있다면, 정점 $u$와 정점 $v$를 연결하는 간선을 추가할 수 없다.
• 정점 $u$와 정점 $v$를 연결하는 간선을 추가하고 난 그래프에서 포함된 간선의 수가 홀수 개인 사이클이 하나라도 존재한다면 그 간선은 추가할 수 없다.

춘배가 조건을 만족하도록 그래프에 간선을 $K$번 추가할 수 있다면 춘배의 승리이다. 그렇지 않다면 춘배의 패배이다.

춘배가 승리할 수 있는지 알아보고 승리할 수 있다면 춘배가 추가해야 하는 간선 $K$개를 찾아보자.

입력

첫째 줄에 $N$과 $K$가 공백으로 구분되어 주어진다. $(1 \le N \le 100,000円,ドル 1ドル \le K \le 300,000円)$

출력

첫째 줄에 춘배가 승리할 수 있다면 YES를, 승리할 수 없다면 NO를 출력한다.

춘배가 승리할 수 있다면, 둘째 줄부터 $K$개의 줄에 걸쳐 춘배가 그래프에 추가해야 하는 간선이 연결하는 두 정점을 한 줄에 하나씩 추가하는 순서대로 출력한다.

제한

힌트