그래프 눌러담기

당신은 최근 국가그래프자원위원회에서 국비로 추진하는 그래프 공급 프로그램에 선정되어 $N$개의 정점을 가진 함수형 그래프를 하나 가지게 되었다. 함수형 그래프란 유향 그래프의 일종인데 각 정점에서 나가는 간선이 정확히 하나인 그래프를 의미한다. 즉, 당신의 그래프는 정점과 간선의 개수가 같다.

하지만 기껏 정점을 잔뜩 마련해 놓고 정점 개수와 같은 수의 간선만 배치하면 정점의 낭비라는 것은 널리 알려진 상식이다. 그래서 당신은 이 그래프에 간선을 더 집어넣고자 한다. 국가그래프자원위원회 또한 혈세가 투입된 그래프에 사용된 정점들이 유용하게 사용되고 있다는 것을 보이기 위해 최대한 많은 간선을 집어넣어야 한다는 데 동의하였고 당신에게 작업을 의뢰했다.

그러나 별다른 제한 조건 없이 그런 작업을 주면 당신이 $1$번 정점과 $2$번 정점 사이에만 간선을 마구 집어넣고 일을 마무리할 것을 뻔히 알고 있는 국가그래프자원위원회에서는 다음과 같은 제한을 두었다.

• 중복 간선을 추가할 수 없다. 즉, 두 정점 $u$와 $v$에 대해 에서 로 가는 간선이 이미 있다면 정점 에서 로 가는 간선을 추가할 수 없다.