16224번 - Path Equality 스페셜 저지

문제

마을 $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$을 출력하여라.

제한

힌트