BOJ 31527 Tournament Matchmaking

문제 링크:

문제 내용

하나의 럭비 팀에는 15개의 포지션이 있으며, 각각의 포지션을 한 사람이 맡아야 합니다. 1명 이상 14명 이하의 럭비 선수들로 이루어진 그룹들을 두 개씩 짝지어 럭비 팀을 구성하려고 합니다. 여러 팀에 같은 그룹이 속할 수 없습니다. 각 선수가 정확히 2가지 포지션을 맡을 수 있을 때, 주어진 그룹들로 만들 수 있는 럭비 팀의 최대 개수를 출력하세요.

입력

첫 줄에는 그룹의 수 $n$이 주어집니다. ($1 \le n \le 500$)

각 그룹에 대해, 첫 줄에는 그 그룹에 속한 선수의 수 $k$가 주어집니다. ($1 \le k \le 14$) 다음 $k$줄에는 각 선수가 맡을 수 있는 두 포지션의 번호 $a$와 $b$가 주어집니다. ($1 \le a < b \le 15$)

출력

문제의 정답을 출력합니다.

문제 풀이