Interesting Graph and Apples

Hexadecimal은 그림 그리기를 좋아한다. 그녀는 이미 유향 그래프와 무향 그래프를 모두 많이 그렸다. 최근에는 «흥미로운 그래프와 사과»라는 정물화를 작업하기 시작했다. 무방향 그래프의 각 정점이 단 하나의 사이클, 즉 재미있는 고리에만 속하고 다른 어떤 사이클에도 속하지 않으면 그 그래프를 흥미롭다고 한다. 재미있는 고리는 모든 정점을 정확히 한 번씩 지나는 사이클이다. 또한 루프도 재미있는 고리이다.

그녀는 이미 사과와 그래프의 일부 간선을 그렸다. 하지만 결과적으로 흥미로운 그래프를 얻으려면 나머지 정점들을 어떻게 연결해야 하는지가 이제 분명하지 않다. 답에는 추가되는 간선이 최소한으로 포함되어야 한다. 더 나아가 답은 사전순으로 가장 작아야 한다. xi ≤ yi인 간선 집합 (x1, y1), (x2, y2), ..., (xn, yn)은, 정수열 x1, y1, x2, y2, ..., xn, yn이 정수열 u1, v1, u2, v2, ..., un, vn보다 사전순으로 작다면, ui ≤ vi인 집합 (u1, v1), (u2, v2), ..., (un, vn)보다 사전순으로 작다. 해내지 못하면 Hexadecimal이 당신을 잡아먹을 것이다. ...산 채로 잡아먹을 것이다.

입력 데이터의 첫 줄에는 각각 정점과 간선의 개수를 나타내는 정수 쌍 n와 m (1 ≤ n ≤ 50, 0 ≤ m ≤ 2500)가 주어진다. 이어지는 줄들에는 이미 간선으로 연결된 정점들을 나타내는 수의 쌍 xi와 yi (1 ≤ xi, yi ≤ n)가 주어진다. 초기 그래프에는 다중 간선과 루프가 있을 수 있다.

첫 줄에 흥미로운 그래프를 구성할 수 있는지 여부에 따라 «YES» 또는 «NO»를 출력한다. 답이 «YES»라면 둘째 줄에 초기 그래프에 추가해야 하는 간선의 개수 k를 출력한다. 마지막으로 k개의 줄에 걸쳐 간선을 그어야 하는 정점 쌍 xj와 yj를 출력한다. 결과에는 다중 간선과 루프가 있을 수 있다. k는 영일 수 있다.