문제

한붓그리기는 주어진 그래프의 원하는 정점에서 시작해 모든 간선을 정확히 한 번씩 지나가는 경로를 말한다.

어떤 정점에서 시작해서 모든 간선을 정확히 한 번 지나갈 수 없다면 한붓그리기가 불가능한 그래프이고, 지나갈 수 있다면 한붓그리기가 가능한 그래프다.

위 그래프는 1 -> 2 -> 5 -> 4 -> 3 -> 2 경로로 이동하거나 2 -> 3 -> 4 -> 5 -> 2 -> 1 경로로 이동하면 한붓그리기가 가능하므로, 한붓그리기가 가능한 그래프다.

반면 위 그래프는 어떤 정점에서 시작해도 한붓그리기가 불가능하므로, 한붓그리기가 불가능한 그래프다.

현빈이는 중요한 과제가 있지만 과제를 하지 않고 제주도로 도망가 버렸다. 도망간 현빈이 대신 과제를 해주자.

과제의 내용은 다음과 같다.

두 정수 과 이 주어질 때, 정점이 개이고 간선이 개이며 한붓그리기가 가능한 단순 무방향 연결 그래프를 구하시오.

즉, 아래 조건을 모두 만족하는 그래프를 만들어야 한다.

• 단순 그래프이므로, 중복 간선과 루프가 없어야 한다. 즉, 임의의 두 정점 사이를 잇는 간선은 최대 하나뿐이어야 하며, 양 끝점이 같은 간선이 있으면 안 된다.
• 연결 그래프이므로, 모든 정점은 간선을 통해 직/간접적으로 연결되어 있어야 한다.

단, 주어지는 은 소수이다. 즉, 의 약수는 과 뿐이다.

조건을 만족하는 모든 입력에 대해 문제에서 요구하는 그래프를 만들 수 있다는 사실을 증명할 수 있다.

입력

첫 번째 줄에 정점의 수를 뜻하는 정수 과 간선의 수를 뜻하는 정수 이 주어진다. N은 소수

출력

개 줄에 걸쳐 각 간선이 연결하는 정점의 번호 와 를 공백으로 구분하여 출력한다.