도미노

도미노 놀이 세트는 크기 2 x 1인 직사각형 조각으로 이루어져 있으며, 각 조각은 짧은 변에 평행한 직선으로 두 개의 같은 반쪽으로 나뉜다. 각 반쪽에는 점이 그려져 있다. 한 반쪽에 그려진 점의 개수는 0부터 M까지의 값을 가진다. 도미노 세트의 조각들은 가능한 모든 서로 다른 순서 없는 숫자 쌍을 가진다. 예를 들어 M = 3이면 해당 도미노 전체 세트는 10개의 조각을 포함한다: {0, 0}, {0, 1}, {0, 2}, {0, 3}, {1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, {3, 3}. 도미노 세트의 조각들은 사슬로 배열될 수 있다. 두 조각은 해당 반쪽에 그려진 점의 개수가 같을 때 짧은 변으로 연결할 수 있다.

전체 세트에서 N개의 조각을 제거했다고 하자(전부는 아니다). 각 조각이 정확히 하나의 사슬에 포함되도록 만들 수 있는 최소 사슬 개수를 구하는 것은 흥미롭다. 주어진 M과 제거된 조각의 목록으로 이 문제를 해결하는 프로그램을 작성하시오.

표준 입력의 첫 번째 줄에는 한 조각의 한 반쪽에 그려질 수 있는 점의 최댓값 M과 제거된 조각의 개수 N이 주어진다. 이어서 N개의 줄이 주어지며, i번째 줄에는 i번째로 제거된 조각의 양쪽 반쪽에 있는 점의 개수 Ai와 Bi가 주어진다.

프로그램은 표준 출력의 첫 번째 줄에 찾은 최소 사슬 개수 V를 출력해야 한다. 다음 V개의 줄 각각에는 찾은 사슬 중 하나를 0부터 M까지의 숫자 수열로 출력해야 하며, 이 수열에서 연속한 두 숫자는 현재 조각의 두 부분에 있는 점의 개수이다. 각 줄의 숫자는 하나의 공백으로 구분한다. 각 수열은 -1로 끝나야 한다.

• 0 ≤ M ≤ 1024

조각의 사슬은 다음과 같다: {2,2}, {2,3}, {3,0}, {0,0}, {0,1}.