정점에 번부터 번까지 번호가 붙은 단순 무향 그래프가 주어진다.
매칭은 어떤 두 간선도 끝점을 공유하지 않는 간선들의 집합이다. 매칭에 포함되는 간선 개수의 최댓값을 구하고, 그 최댓값을 달성하는 매칭을 하나 출력하여라.
입력은 다음과 같은 형식으로 주어진다.
첫째 줄에 최대 매칭의 크기 를 출력한다.
그 다음 개의 줄에 걸쳐 매칭에 포함되는 간선의 두 끝점 를 공백으로 구분하여 출력한다.
두 간선 와 는 끝점을 공유하지 않는다. 정점이 개이므로 크기가 보다 큰 매칭은 존재할 수 없다.
각 ()에 대해 번 정점과 번 정점을 잇는 간선이 존재한다.
출력한 각 순서쌍 는 입력으로 주어진 간선이어야 하며, 어떤 정점도 두 번 이상 등장해서는 안 된다. 가능한 답이 여러 가지라면 아무거나 출력해도 된다.
삼각형에서는 서로 다른 두 간선이 항상 하나의 정점을 공유하므로 최대 매칭의 크기는 이다.
