거의 이분 그래프의 최대 매칭

시간 제한2초메모리 제한128 MB

요약

두 경로 A와 B를 최대 50개의 교차 간선으로 연결한 거의 이분 그래프에서 최대 매칭의 크기를 구하는 문제입니다.

난이도: 어려움10점 중 9점
유형: 그래프, 동적 계획법, 조합론, 그리디
정답자: 아직 제출이 없습니다

문제

그래프의 매칭은 서로 끝점을 공유하지 않는 간선들의 집합이다. 최대 매칭은 가능한 매칭 중 간선 수가 가장 많은 매칭이다.

이분 그래프는 모든 정점을 두 집합 A와 B로 나눌 수 있고, 모든 간선이 A의 정점 하나와 B의 정점 하나를 잇는 그래프이다. 이분 그래프의 최대 매칭은 최대 유량 알고리즘으로 구할 수 있다.

거의 이분 그래프는 정점이 A = {A1, A2, ..., AnA}와 B = {B1, B2, ..., BnB}로 나뉜다. A와 B 사이를 잇는 간선이 M개 주어지며, 여기에 Ai와 Ai+1을 잇는 간선 (1 <= i <= nA-1), Bj와 Bj+1을 잇는 간선 (1 <= j <= nB-1)이 추가된다. 따라서 정점 수가 nA + nB인 거의 이분 그래프의 간선 수는 M + nA - 1 + nB - 1이다.

nA, nB와 A와 B 사이를 잇는 M개의 간선이 주어질 때, 이 거의 이분 그래프의 최대 매칭 크기를 구하라.

입력

첫째 줄에 nA와 nB가 주어진다. 둘째 줄에 A와 B 사이를 잇는 간선의 개수 M이 주어진다. 다음 M개의 줄에는 간선 정보 i j가 주어지며, 이는 Ai와 Bj를 잇는 간선을 의미한다.

출력

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

제한

1 <= nA, nB <= 1,000
0 <= M <= 50
1 <= Ai <= nA
1 <= Bj <= nB

예제4

예제 1
입력
```
6 6
4
1 3
1 5
3 6
4 2
```
예상 출력
```
6
```
예제 2
입력
```
3 3
3
1 1
2 2
3 3
```
예상 출력
```
3
```
예제 3
입력
```
3 3
2
1 2
2 3
```
예상 출력
```
2
```

예제 4

입력

예상 출력