시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (언어별 추가 시간 없음) 1024 MB 131 60 12 30.000%

문제

마을 $N$개로 이루어진 나라 X가 있다. 각 마을에는 $1$번부터 $N$번까지 순서대로 번호가 붙어있다. 

X의 지도자가 신뢰하는 브레인 중 한 명인 준원이는 지금 어려운 상황에 놓여있다.

준원이는 각 마을 사이를 잇는 여러 개의 일방통행 도로들을 건설해야 하는 일을 수행해야 한다. 단, 한 마을 $u$에서 다시 $u$로 가는 도로도 존재할 수 있고, 마을 $u$, $v$에 대해 $u$에서 $v$로 가는 도로는 최대 하나다. 마을 $u$에서 $u$로 가는 도로 역시 최대 하나다. 준원이는 특정 마을들끼리만 서로 협력하는 일을 방지하고, 모든 마을이 다함께 친목을 도모하게 하기 위하여 다음 조건을 만족하도록 도로를 설계하고자 한다.

조건: 임의의 두 마을 $u$, $v$에 대하여 $u$에서 $v$로 가는 길이가 2인 서로 다른 경로의 개수가 정확히 $M$개이다. 단, $u$와 $v$는 같은 마을이 될 수 있다.

주어진 $N$과 $M$에 대하여, 준원이가 조건을 만족하도록 도로를 설계할 수 있을 지 판별하고, 가능할 경우 그렇게 할 수 있는 방법을 하나 제시하자.

입력

$N$, $M$이 한 줄에 차례대로 입력된다. 입력은 $1 \le N \le 500$, $1 \le M \le 5000$를 만족한다.

출력

준원이의 목표가 달성 가능하다면, 그 예시를 다음 형식으로 출력하여라. 

첫째 줄에는 준원이가 건설해야 하는 도로의 개수 $E$를 출력한다. 

두번째 줄부터 $E+1$번째 줄까지는, $i$번째 줄에 준원이가 건설할 $i-1$번째 도로의 출발 마을과 도착 마을의 번호를 순서대로 출력한다. 

준원이가 목표를 달성하는 것이 불가능하면, $-1$을 출력하여라.

예제 입력 1

3 3

예제 출력 1

9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

예제 입력 2

5 4

예제 출력 2

-1

출처

Contest > 웰노운컵 > 제2회 웰노운컵 Day 2 A번