33977번 - $K$-POP 스페셜 저지

K-POP은 한국의 대중문화이다. SCSC의 동아리방에 거주하는 수인이는 PS를 한국의 새로운 대중문화로 만들고자, $K$-POP을 다음과 같이 새로 정의하였다.

어떤 이진 트리 $T$가 양의 정수 $K$에 대해 다음 조건을 만족하면, $T$는 $K$-POP(Perfect Outcome of Product)이라고 한다.

• $T$의 리프 노드의 수와 리프 노드가 아닌 노드의 수의 곱이 $K$이다.

이때 이진 트리는 모든 노드의 자식 노드의 수가 $2$ 이하인 루트 있는 트리를, 리프 노드는 이진 트리에서 자식 노드의 수가 $0$인 노드를 의미한다.

양의 정수 $K$가 주어질 때, $K$-POP들 중 노드 수가 최소인 $K$-POP 중 하나를 출력하시오.

첫째 줄에 정수 $K$가 주어진다. $(1 \le K \le 100\,000)$

첫째 줄에 $K$-POP의 노드 수의 최솟값 $N$을 출력한다.

루트 노드 $1$과 루트가 아닌 노드 $2$, $3$, $\cdots$, $N$으로 구성된 $K$-POP을 구성하여, 둘째 줄부터 $N-1$개의 줄에 간선에 대한 정보를 하나씩 출력한다.

$i$번째 줄에는 $i$번째 간선이 연결하는 두 정점 $a_i$와 $b_i$를 공백으로 구분하여 출력한다. $(1 \le a_i, b_i \le N)$

입력 조건을 만족하는 모든 $K$에 대해 $K$-POP이 항상 존재함을 증명할 수 있다.