33994번 - Magical Trees 스페셜 저지

라즈, 쉬폰, 솔트는 'CAFE MiLK'라는 이름의 카페를 운영하고 있다. 카페의 외관을 꾸미려는 셋은 마당에 인조 나무 세 그루를 심기로 했다.

세 명은 $N$개의 정점으로 이루어진 트리 세 개를 만들려고 한다. $S$를 각 트리에 사용된 간선 $(u, v)$ $(u < v)$를 모두 모은 multiset이라고 하자. 이때 $S$의 임의의 원소 $e$에 대해, $e$는 항상 $S$에서 정확히 두 번 등장해야 한다.

위 조건을 만족하는 트리 세 개를 만들 수 있는지 확인하고, 만들 수 있다면 어떻게 만들 수 있는지 알려주자!

첫 번째 줄에 정수 $N$이 주어진다. $(2 \leq N \leq 300\ 000)$

조건을 만족하도록 트리를 만들 수 없다면 No를 출력한다.

아니라면 Yes를 출력하고, 다음 $3N-3$개의 줄에 각 트리의 간선 $(u, v)$ $(1 \leq u < v \leq N)$를 u v의 형식으로 출력한다. 이는 트리에 $u$번 정점과 $v$번 정점을 연결하는 간선이 존재함을 의미한다. 처음 $N-1$개의 줄에는 첫 번째 트리의 간선, 그다음 $N-1$개의 줄에는 두 번째 트리의 간선, 마지막 $N-1$개의 줄에는 세 번째 트리의 간선을 출력한다.

multiset은 중복 원소를 허용하는 집합이다.