#51 일반 그래프 최대 매칭 복원

問題を読み込み中...

本文、提出履歴、提出フォームを準備しています。

#51 일반 그래프 최대 매칭 복원

Statement

問題文の言語

정점에 $1$ 번부터 $N$ 번까지 번호가 붙은 단순 무향 그래프가 주어진다.

매칭은 어떤 두 간선도 끝점을 공유하지 않는 간선들의 집합이다. 매칭에 포함되는 간선 개수의 최댓값을 구하고, 그 최댓값을 달성하는 매칭을 하나 출력하여라.

입력은 다음과 같은 형식으로 주어진다.

$N\ M$ $u_1\ v_1$ $u_2\ v_2$ $\vdots$ $u_M\ v_M$

각 $i$ ( $1 \leq i \leq M$ )에 대해 $u_i$ 번 정점과 $v_i$ 번 정점을 잇는 간선이 존재한다.

첫째 줄에 최대 매칭의 크기 $K$ 를 출력한다.

그 다음 $K$ 개의 줄에 걸쳐 매칭에 포함되는 간선의 두 끝점 $a_i,b_i$ 를 공백으로 구분하여 출력한다.

출력한 각 순서쌍 $(a_i,b_i)$ 는 입력으로 주어진 간선이어야 하며, 어떤 정점도 두 번 이상 등장해서는 안 된다. 가능한 답이 여러 가지라면 아무거나 출력해도 된다.

#	得点	制約
1	20	$N \leq 24$ .
2	80	추가적인 제약조건이 없다.

例 1

入力例

出力例

2
1 2
3 4

두 간선 $(1,2)$ 와 $(3,4)$ 는 끝점을 공유하지 않는다. 정점이 $4$ 개이므로 크기가 $2$ 보다 큰 매칭은 존재할 수 없다.

例 2

入力例

出力例

1
2 3

삼각형에서는 서로 다른 두 간선이 항상 하나의 정점을 공유하므로 최대 매칭의 크기는 $1$ 이다.