====== 복수전공 ======

===== 풀이 =====
  * 강의를 노드로, 겹치는 관계를 엣지로 연결해주자. 다른 학부의 강의들 사이에서만 엣지가 존재하기 때문에 이분 그래프가 된다.
  * 겹치지 않는 강의들을 최대한 많이 고르는 것은 최대 독립집합을 구하는 문제가 되고, 전체 노드 갯수에서 최소 버텍스 커버의 크기를 빼주면 최대 독립집합의 크기를 구할수 있다. 이분그래프이기 때문에 [[ps:이분 매칭#쾨닉의 정리]]에 따라서 최소 버텍스 커버의 크기는 최대 매칭의 크기와 같다. 결국 답은 n에서 이분매칭의 크기를 빼주면 된다. 
  * 시간복잡도는 [[ps:이분 매칭]]을 구하는데에 O(VE)가 걸린다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 12843. 복수전공".

- Problem link: https://www.acmicpc.net/problem/12843
- Solution link: http://www.teferi.net/ps/problems/boj/12843

Tags: [Bipartite Matching]
"""

import sys
from teflib import tgraph


def main():
    # pylint: disable=unused-variable
    n, m = [int(x) for x in sys.stdin.readline().split()]
    bigraph = [[] for _ in range(n)]
    comp_lectures = set()
    for _ in range(n):
        lecture, dep = sys.stdin.readline().split()
        if dep == 'c':
            comp_lectures.add(int(lecture))
    for _ in range(m):
        lecture1, lecture2 = [int(x) for x in sys.stdin.readline().split()]
        if lecture1 in comp_lectures:
            bigraph[lecture1 - 1].append(lecture2 - 1)
        else:
            bigraph[lecture2 - 1].append(lecture1 - 1)

    print(n - len(tgraph.bipartite_matching(bigraph)))


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:tgraph#bipartite_matching|teflib.tgraph.bipartite_matching]]

{{tag>BOJ ps:problems:boj:플래티넘_3}}