그래프 동형

그래프 동형은 컴퓨터 과학에서 중요한 문제이다. 이 문제를 다항 시간에 푸는 알고리즘이 존재하는지는 알려져 있지 않으며, NP-완전인지도 알려져 있지 않다.

두 무방향 그래프 $G$와 $H$는 정점 수가 같고, 전단사 함수 $\varphi:VG \to VH$가 존재하여 $G$에 간선 $uv$가 있을 때와 그때만 $H$에 간선 $\varphi(u)\varphi(v)$가 있으면 동형이다. 동형에서 변하지 않는 그래프의 성질은 여럿 있으며, 그중 하나가 차수 프로파일(degree profile)이다.

정점 $u$의 차수 $\deg(u)$는 간선으로 $u$와 연결된 다른 정점의 수이다. 연결된 무방향 그래프 $G$의 정점 수가 $n$일 때, 각 정점 $u$에 대해 $u$로부터 거리가 $0, 1, \ldots, n-1$인 정점 집합 $V_{u,0}, V_{u,1}, \ldots, V_{u,n-1}$을 구한다. 일부 집합은 비어 있을 수 있다. 각 집합에 대해, 그 집합에 속한 정점들의 차수를 원소로 하는 다중집합 $D_{u,i}$를 구한다. 이 목록 $D_u = [D_{u,0}, D_{u,1}, \ldots, D_{u,n-1}]$을 정점 $u$의 차수 프로파일이라 한다. 그래프의 모든 정점에 대한 차수 프로파일을 모은 다중집합이 그 그래프의 차수 프로파일이다.

아래 그래프의 차수 프로파일은 $\big\{[\{1\},\{2\},\{1\}], [\{2\},\{1,1\},\varnothing], [\{1\},\{2\},\{1\}]\big\}$이다.

차수 프로파일은 동형에서 변하지 않는다. 하지만 차수 프로파일이 같아도 동형이 아닌 그래프가 있다. 아래 두 그래프가 그런 예이다. 두 그래프에서 차수가 2인 정점들의 차수 프로파일은 $[\{2\}, \{3, 3\}, \{3, 3\}, \{2\}, \varnothing, \varnothing]$이고, 차수가 3인 정점들의 차수 프로파일은 $[\{3\}, \{2, 3, 3\}, \{2, 3\}, \varnothing, \varnothing, \varnothing]$이다. 그러나 두 그래프는 명백히 동형이 아니다.

차수 프로파일이 다르면 두 그래프가 동형이 아님을 증명할 수 있다. 차수 프로파일이 같으면 동형 사상을 찾는 쉬운 방법이 없다. 같은 프로파일을 가진 정점끼리 대응시키기가 어려울 수 있기 때문이다. 그러나 모든 정점이 서로 다른 차수 프로파일을 갖는 그래프 종류가 있다. 이런 그래프를 차수 구분 가능(degree distinguishable)하다고 부르자. 차수 구분 가능한 그래프에서는 차수 프로파일만으로 동형 여부를 쉽게 확인할 수 있다.

그러나 차수 구분 가능한 그래프라도 차수 프로파일이 같고 동형이 아닌 경우가 있다. 주어진 $n$에 대해, 정점이 $n$개인 연결된 차수 구분 가능 그래프 두 개를 찾으시오. 두 그래프는 동형이 아니어야 하며, 차수 프로파일은 같아야 한다.

입력 파일은 정수 $n$ ($3 \le n \le 100$) 하나를 포함한다.

정점이 $n$개이고, 차수 구분 가능하며, 차수 프로파일이 같고, 서로 동형이 아닌 그래프 두 개가 존재하지 않으면 첫 줄에 "NO"를 출력한다. 그렇지 않으면 "YES"를 출력하고, 이어서 그래프 두 개의 설명을 출력한다.

각 설명은 간선 수 $m$으로 시작하고, 그 뒤에 간선으로 연결된 정점 쌍을 $m$개 출력한다. 두 정점 사이의 간선은 최대 하나여야 하며, 정점을 자기 자신과 잇는 간선은 있으면 안 된다.

각 그래프의 정점은 1부터 $n$까지 번호를 매겨야 한다. 두 그래프에서 번호 $i$인 정점은 같은 차수 프로파일을 가져야 한다. 같은 그래프 안의 두 정점은 같은 차수 프로파일을 가지면 안 된다.

두 번째 예제는 차수 프로파일이 같고 차수 구분 가능하지 않은, 동형이 아닌 두 그래프를 보여준다. 이는 출력 형식을 보이기 위해 주어진 것이다. $n = 6$에 대해 이런 형태로 출력하면 정답으로 인정되지 않는다.