독립 간선 집합과 인증서

$G$를 단순 무방향 그래프라고 하자. $G$의 두 정점이 간선으로 이어져 있으면 두 정점은 인접하다고 하고, $G$의 두 간선이 정점을 공유하면 두 간선은 인접하다고 한다. 아래 그림 1(a)의 그래프에서 정점 $3$과 정점 $4$는 간선 $(3,4)$로 이어져 있으므로 인접하다. 간선 $(3,4)$와 간선 $(3,5)$는 정점 $3$을 공유하므로 인접하다.

정점 집합의 부분집합 가운데 어떤 두 정점도 인접하지 않은 것을 독립 정점 집합이라고 한다. 간선 집합의 부분집합 가운데 어떤 두 간선도 인접하지 않은 것을 독립 간선 집합이라고 한다. 크기가 가장 큰 독립 정점 집합의 크기를 정점 독립수라고 하고 $\alpha(G)$로 쓴다. 같은 방식으로 크기가 가장 큰 독립 간선 집합의 크기를 간선 독립수라고 하고 $\nu(G)$로 쓴다.

그림 1. 그래프 $G_1$과 $G_2$. (a) $\alpha(G_1) = 4$, $\nu(G_1) = 4$인 그래프 $G_1$. (b) $\alpha(G_2) = 6$, $\nu(G_2) = 3$인 그래프 $G_2$.

독립 간선 집합 문제는 그래프에서 크기가 최대인 독립 간선 집합을 찾는 문제다. 이 문제는 오래 연구되어, 그래프 크기의 다항 시간에 끝나는 알고리즘이 여러 개 나와 있다. 그런데 프로그램이 입력 $X$에 대해 답 $Y$를 내놓아도, 사용자는 $Y$가 정말 옳은 답인지 버그 때문에 망가진 답인지 알 수 없다. 인증 알고리즘은 답과 함께 인증서 $Z$를 내놓는 알고리즘이다. 사용자는 $Z$를 직접 살펴보거나 검사기 프로그램에 넣어서 답이 옳다고 확인하거나, 답을 버그가 있는 것으로 판단해 버린다.

이분 그래프에서 독립 간선 집합 문제의 인증서로 무엇이 좋은지 생각해 보자. 정점 집합을 서로소인 두 집합 $U$와 $V$로 나눌 수 있고 모든 간선이 $U$의 정점 하나와 $V$의 정점 하나를 잇는 그래프를 이분 그래프라고 한다. 그림 1의 두 그래프는 모두 이분 그래프이고, 주황색 정점과 파란색 정점이 각각 한쪽을 이룬다. 쾨니그 정리에 따르면 정점이 $n$개인 이분 그래프 $G$는 항상 $\nu(G) + \alpha(G) = n$을 만족한다. 그래서 최대 독립 정점 집합이 좋은 인증서가 된다. 정점이 $n$개인 이분 그래프에서 크기 $k$의 독립 간선 집합과 크기 $n - k$의 독립 정점 집합을 함께 찾았다면 $\nu(G) = k$이고 $\alpha(G) = n - k$이므로, 찾은 두 집합은 둘 다 최대다.

이분 그래프 $G$가 주어진다. 최대 독립 간선 집합 $Y$와, 인증서로 쓸 최대 독립 정점 집합 $Z$를 찾아 출력하라. 정점에는 $1$번부터 $n$번까지 번호가 붙어 있다. 검사기는 $Y$에 속한 두 간선이 서로 인접하지 않음을 확인하고, $Z$에 속한 두 정점이 서로 인접하지 않음을 확인한 뒤, $|Y| + |Z| = n$이면 답을 받아들인다.

첫째 줄에 그래프의 정점 개수 $n$과 간선 개수 $m$이 공백을 두고 주어진다. ($1 \le n \le 1000$, $1 \le m \le 50000$)

다음 $m$개의 줄에 간선이 한 개씩 주어진다. 각 줄에는 그 간선이 잇는 두 정점의 번호 $u$와 $v$가 공백을 두고 주어진다. ($1 \le u, v \le n$, $u \neq v$)

주어지는 그래프는 단순 이분 그래프이며, 연결 그래프가 아닐 수도 있다. 같은 간선이 두 번 주어지지 않는다.

첫째 줄에 최대 독립 간선 집합의 크기 $k$를 출력한다.

다음 $k$개의 줄에 그 집합에 속한 간선을 한 개씩 출력한다. 간선은 두 정점 번호를 작은 번호부터 큰 번호 순서로 출력한다. 줄은 첫 번호가 작은 것부터 출력하고, 첫 번호가 같으면 둘째 번호가 작은 것부터 출력한다. 최대 독립 간선 집합이 여러 개면, 이렇게 정렬한 간선 목록이 사전순으로 가장 앞서는 집합을 출력한다.

그 다음 줄에 인증서의 크기 $k'$을 출력하고, 이어지는 줄에 인증서에 속한 정점 번호를 오름차순으로 공백을 두고 출력한다. 최대 독립 정점 집합이 여러 개면, 오름차순으로 정렬한 정점 목록이 사전순으로 가장 앞서는 집합을 출력한다.

두 규칙을 모두 지키는 출력은 하나뿐이다.