어느 학교에 학생 \(N\)명과 방과후 강좌 \(M\)개가 있다. 학생들은 각각 듣고 싶은 강좌 목록을 제출했다.

한 학생은 강좌를 최대 하나만 들을 수 있고, 한 강좌에는 학생이 최대 한 명만 들어갈 수 있다. 학생은 자신이 희망한 강좌에만 배정될 수 있다.

강좌에 배정되는 학생 수의 최댓값을 구하시오.

이분 매칭이란?

정점을 두 그룹으로 나눴을 때, 간선이 항상 서로 다른 그룹 사이에만 있는 그래프를 이분 그래프라고 한다.

이 문제에서는 학생이 한 그룹, 강좌가 다른 그룹이고, "학생 \(i\)가 강좌 \(j\)를 희망한다"가 간선이다.

매칭이란 어떤 정점도 두 번 이상 쓰이지 않도록 고른 간선들의 집합이다.

즉, 학생 한 명과 강좌 하나를 짝짓되 겹치지 않게 짝지은 것이다.

짝의 개수가 가장 많은 매칭을 최대 매칭이라고 하며, 이 문제의 답이 바로 최대 매칭의 크기이다.

풀이 방법 (Kuhn 알고리즘)

학생을 1번부터 차례대로 보면서, 그 학생을 어떤 강좌에 넣을 수 있는지 시도한다. 핵심은 "이미 다른 학생이 차지한 강좌라도, 그 학생을 다른 강좌로 옮길 수 있다면 자리를 빼앗을 수 있다" 는 것이다.

학생 \(i\)를 배정하는 함수 try_match(i)는 다음과 같이 동작한다.

1. 학생 \(i\)가 희망하는 강좌 \(j\)를 하나씩 본다.
2. 이번 시도에서 이미 방문한 강좌 \(j\)라면 건너뛴다. 처음 보는 강좌라면 방문 표시를 한다.
3. 강좌 \(j\)가 비어 있으면, 학생 \(i\)를 \(j\)에 배정하고 성공을 반환한다.
4. 강좌 \(j\)를 학생 \(k\)가 차지하고 있다면, try_match(k)를 호출해 \(k\)를 다른 강좌로 옮겨 본다. 옮기는 데 성공하면 학생 \(i\)를 \(j\)에 배정하고 성공을 반환한다.
5. 모든 희망 강좌에서 실패하면 실패를 반환한다. 학생마다 방문 표시를 초기화한 뒤 try_match를 호출하고, 성공한 횟수를 세면 그것이 최대 매칭의 크기이다.

예를 들어 예제 1에서 학생 1은 강좌 1에 배정된다. 학생 2는 강좌 1만 희망하는데, 강좌 1의 주인인 학생 1을 강좌 2로 옮길 수 있으므로 학생 2가 강좌 1을 차지한다.

학생 3은 강좌 2를 시도하지만 학생 1이 이미 있고, 학생 1은 다른 곳으로 갈 수 없으므로 실패한다.

대신 강좌 3이 비어 있어 학생 3은 강좌 3에 배정된다. 따라서 답은 \(3\)이다.

왜 이 방법이 최대 매칭을 찾는가?

증가 경로. 아직 배정되지 않은 학생에서 출발해 "희망 강좌로 이동 → 그 강좌의 주인 학생으로 이동 → 그 학생의 다른 희망 강좌로 이동 → …"을 반복하다가

빈 강좌에 도착하는 경로를 증가 경로라고 한다.

증가 경로를 따라 모든 학생을 한 칸씩 옮기면, 원래 배정된 학생은 모두 그대로 배정된 채로 새 학생 한 명이 추가로 배정된다.

try_match(i)가 성공한다는 것은 학생 \(i\)에서 시작하는 증가 경로를 찾아 이렇게 옮긴다는 뜻이다.

사실 1. 증가 경로가 없으면 최대 매칭이다. 현재 매칭 \(A\)보다 큰 매칭 \(B\)가 있다고 하자.

\(A\)와 \(B\) 중 정확히 한쪽에만 속하는 간선들을 모아 보면, 각 정점은 \(A\) 간선 최대 하나, \(B\) 간선 최대 하나에만 닿으므로 이 간선들은 \(A\)와 \(B\)가 번갈아 나오는 경로나 사이클로 나뉜다.

사이클과 길이가 짝수인 경로는 \(A\), \(B\) 간선 수가 같다. 그런데 \(B\)의 간선이 더 많으므로, \(B\) 간선으로 시작해 \(B\) 간선으로 끝나는 경로가 적어도 하나 있어야 한다.

이 경로의 양 끝은 \(A\)에서 배정되지 않은 학생과 빈 강좌이므로, 이것이 바로 \(A\)의 증가 경로이다. 따라서 증가 경로가 없다면 더 큰 매칭도 없다.

사실 2. 한 번 실패한 학생은 나중에도 실패한다. try_match(i)가 실패하면, 그 시도에서 방문한 강좌들은 모두 차 있고, 그 주인 학생들이 희망하는 강좌도 전부 방문한 강좌 안에 있다.

즉 이 강좌·학생 묶음은 바깥의 빈 강좌로 빠져나갈 길이 없는 닫힌 묶음이다.

이후 다른 학생의 증가 경로가 이 묶음에 들어오면 빈 강좌에 도달할 수 없으므로, 이후의 어떤 증가 경로도 이 묶음을 지나지 않는다.

묶음이 그대로 유지되므로 학생 \(i\)는 끝까지 증가 경로를 가질 수 없다.

알고리즘이 끝났을 때 사실 2에 의해 어떤 미배정 학생에게도 증가 경로가 없고, 사실 1에 의해 그때의 매칭이 최대 매칭이다.

입력

첫째 줄에 학생 수 \(N\), 강좌 수 \(M\), 희망 정보의 개수 \(K\)가 공백으로 구분되어 주어진다.

둘째 줄부터 \(K\)개의 줄에 걸쳐 두 정수 \(a\)와 \(b\)가 공백으로 구분되어 주어진다. 이는 학생 \(a\)가 강좌 \(b\)를 희망한다는 뜻이다.

출력

강좌에 배정될 수 있는 학생 수의 최댓값을 출력한다.

제한 사항

• \(1 \le N, M \le 500\)
• \(0 \le K \le 10,000\)
• \(1 \le a \le N\)
• \(1 \le b \le M\)
• 같은 \((a, b)\) 쌍은 두 번 이상 주어지지 않는다.

예제 입력 1

3 3 5
1 1
1 2
2 1
3 2
3 3

예제 출력 1

3

예제 입력 2

4 3 5
1 1
2 1
3 1
3 2
4 1

예제 출력 2

2

노트

예제 2에서 학생 1, 2, 4는 모두 강좌 1만 희망하므로 이 셋 중 한 명만 배정될 수 있다.

학생 3은 강좌 2에 배정할 수 있으므로 답은 \(2\)이다. 강좌 3은 아무도 희망하지 않아 비어 있게 된다.