버스 노선

시간 제한1초메모리 제한512 MB

요약

1부터 n까지의 정점으로 이루어진 연결 그래프에서 각 간선 양 끝점의 합이 모두 다르도록 간선 m개를 구성하고, 불가능하면 -1을 출력한다.

난이도: 보통10점 중 6점
유형: 그래프, 그리디, 구현, 수학
정답자: 아직 제출이 없습니다

문제

수년간 대중교통이 없던 도시 Krockholm에 마침내 버스 노선망이 생긴다. 계획은 아직 설계 단계에 있지만, $1$ 번부터 $n$ 번까지 번호가 붙은 $n$ 개의 정거장과 두 정거장을 잇는 $m$ 개의 버스 노선을 두기로 결정되었다. 남은 일은 어떤 정거장 쌍을 연결할지 정하는 것뿐이다. 중요한 조건이 하나 있는데, 어떤 정거장에서든 다른 어떤 정거장으로도 갈 수 있어야 한다. 여기에 더해 누군가 버스 노선에 양 끝 정거장 번호의 합을 이름으로 붙이자는 기발한 생각을 했다. 따라서 이 합들은 모두 달라야 한다.

두 정수 $n$ 과 $m$ 이 주어진다. $1$ 번부터 $n$ 번까지 번호가 붙은 $n$ 개의 정점과 $m$ 개의 간선으로 이루어진 그래프를 만들어 다음 조건을 만족시켜라.

그래프는 연결되어 있다.
간선 양 끝 정점 번호의 합은 모두 다르다.

입력

입력은 한 줄로 이루어지며 두 정수 $n$ 과 $m$ 이 주어진다. ( $2 \leq n \leq 100$ , $1 \leq m \leq 10^4$ )

출력

주어진 조건을 만족하는 그래프를 만들 수 없으면 "-1"을 출력한다. 그렇지 않으면 $m$ 개의 줄을 출력하며, $i$ 번째 줄에는 $i$ 번째 간선의 양 끝 정점 $a\_i$ , $b\_i$ 를 출력한다. 가능한 답이 여러 개라면 그중 아무거나 출력해도 된다.

예제3

예제 1
입력
```
4 4
```
예상 출력
```
2 1
2 3
4 3
4 2
```
예제 2
입력
```
10 100
```
예상 출력
```
-1
```
예제 3
입력
```
10 1
```
예상 출력
```
-1
```