Uuu

이 분자는 예제의 그래프에 대응한다.

운운닐륨(Uuu)은 원자번호 111번 화학 원소의 이름이었으나, 2004년에 뢴트게늄(Rg)으로 바뀌었다. 이런 무거운 원소는 매우 불안정해서 몇몇 연구소에서만 합성되었다.

여러분은 이런 연구소 중 한 곳에 채용되어 시뮬레이션에 쓰이는 알고리즘을 최적화하게 되었다. 예를 들어 복잡한 화학 반응을 시뮬레이션할 때는 입자가 몇 개인지 추적하는 것이 중요한데, 이는 그래프의 연결 요소 개수를 세어서 한다.

현재 연구소에는 무방향 그래프를 입력받아 연결 요소 개수를 출력하는 파이썬 코드가 있다(첨부 파일 참고). 보다시피 이 코드는 모두가 좋아하는 자료 구조인 유니온 파인드를 사용한다.

코드를 한동안 살펴본 여러분은 코드에 버그가 있다는 것을 알아낸다! 코드는 여전히 올바른 답을 내지만, 이 버그 때문에 비효율적으로 실행될 수 있다. 여러분의 과제는 주어진 정점 수와 간선 수를 가진 그래프를 만들어서 코드가 아주 느리게 실행되도록 하는 것이다. while 문 안에 있는 세 번째 줄이 몇 번 실행되는지 셀 것이고, 여러분의 프로그램은 이 횟수에 따라 점수를 받는다.

입력은 정수 $N$과 $M$이 한 줄에 주어지며, 이는 여러분의 그래프가 가져야 하는 정점 수와 간선 수이다. 예제를 제외하면 테스트 케이스는 $N = 100$, $M = 500$인 하나뿐이다.

출력은 $M$개의 줄로 이루어지며, $i$번째 줄에는 두 정수 $u\_i$와 $v\_i$ ($1 \leq u\_i, v\_i \leq N$)가 주어진다. 이는 여러분의 그래프에서 정점 $u\_i$와 $v\_i$가 간선으로 연결되어 있음을 나타낸다.

여러분의 그래프에는 중복 간선이나 자기 자신으로 향하는 간선이 있으면 안 된다. 즉, $u\_i$는 $v\_i$와 달라야 하고 모든 집합 $\{u\_i, v\_i\}$는 서로 달라야 한다.

예제에서 출력은 가장 안쪽 루프가 $20$번 실행되게 하는 그래프를 담고 있다. 코드를 실행해서 직접 확인해 보자!