시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB34513511343.969%

문제

그래프의 최대 매칭 (Maximum Matching)은 두 간선이 같은 정점을 공유하지 않는 간선의 최대 집합을 말한다.

이분 그래프 (Bipartited Graph)는 그래프의 모든 정점을 두 집합 A와 B로 나눌 수 있는 그래프이다. 모든 간선의 끝 점은 A에 하나, B에 하나 있어야 한다. 이분 그래프에서 최대 매칭을 구하는 문제는 Maximum Flow 알고리즘을 이용해서 풀 수 있다.

거의 이분 그래프는 모든 정점이 집합 A = {A1, A2, …, AnA}와 B = {B1, B2, …, BnB}로 나누어져 있고, 모든 간선의 끝 점은 A에 하나, B에 하나있는 그래프이다. 여기까지는 이분 그래프와 동일한 모양을 갖는다. 거의 이분 그래프는 이분 그래프와 다르게 nA-1 + nB-1개의 간선을 추가로 가진다. 추가가 되는 간선은 Ai에서 Ai+1로 가는 간선 (1 ≤ i ≤ nA-1)과 Bi에서 Bi+1로 가는 간선 (1 ≤ i ≤ nB-1)이다. 따라서, 끝 점이 A에 하나, B에 하나 있는 간선의 개수를 M이라고 했을 때, 정점의 수가 nA + nB인 거의 이분 그래프의 간선의 개수는 M + nA-1 + nB-1이 된다.

거의 이분 그래프의 정점의 개수를 나타내는 nA, nB와 A와 B에 끝점을 두고 있는 간선 M개가 입력으로 주어졌을 때, 최대 매칭을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 nA와 nB가 주어진다. 둘째 줄에는 A와 B에 끝점을 두고 있는 간선의 개수 M이 주어진다. 다음 M개의 줄에는 간선의 정보가 i j와 같은 형식으로 주어지며, i는 집합 A의 정점 Ai, j는 B의 정점 (Bj)를 의미한다.

출력

첫째 줄에 입력으로 주어진 거의 이분 그래프의 최대 매칭의 수를 출력한다.

제한

  • 1 ≤ nA, nB ≤ 1,000
  • 0 ≤ M ≤ 50
  • 1 ≤ Ai ≤ nA
  • 1 ≤ Bj ≤ nB

예제 입력 1

6 6
4
1 3
1 5
3 6
4 2

예제 출력 1

6

예제 입력 2

3 3
3
1 1
2 2
3 3

예제 출력 2

3

예제 입력 3

3 3
2
1 2
2 3

예제 출력 3

2

예제 입력 4

13 16
17
6 8
3 4
7 11
3 13
8 1
3 1
8 4
7 5
3 8
7 3
2 6
4 3
1 15
11 16
13 2
12 2
11 2

예제 출력 4

14

출처