해밀턴

시간 제한2초메모리 제한512 MB

요약

K가 주어질 때, 정점이 최대 20개인 그래프를 만들어 해밀턴 경로로 이어지는 정점 쌍이 정확히 K개가 되도록 합니다. 그래프의 간선 목록을 출력합니다.

난이도: 어려움10점 중 8점
유형: 구현, 그래프, 비트 연산
정답자: 아직 제출이 없습니다

문제

양의 정수 $K \le 60$ 이 주어진다. 정점이 20개 이하인 그래프를 구성하라. 이 그래프에는 해밀턴 경로가 존재하는 순서 없는 정점 쌍 $(u, v)$ 가 정확히 $K$ 개 있어야 한다. 이 제약 조건에서 해가 항상 존재함은 증명되어 있다. 해밀턴 경로는 그래프의 두 정점 사이의 경로로, 모든 정점을 정확히 한 번씩 방문한다.

입력

입력은 한 줄이며, 정수 $K$ ( $1 \le K \le 60$ )가 주어진다.

출력

첫 줄에 두 정수 $n$ , $m$ ( $2 \le n \le 20$ , $0 \le m \le \frac{n(n-1)}{2}$ )을 출력한다. 각각 정점 수와 간선 수이다. 다음 $m$ 개의 줄에는 간선 $(u, v)$ 를 한 줄에 하나씩 출력한다 ( $1 \le u, v \le n$ , $u \neq v$ ). 모든 간선은 서로 달라야 한다.

예제3

예제 1
입력
```
1
```
예상 출력
```
2 1
1 2
```
예제 2
입력
```
2
```
예상 출력
```
4 4
1 2
1 3
2 3
3 4
```
예제 3
입력
```
3
```
예상 출력
```
3 3
1 2
2 3
3 1
```