리눅스 패키지들이 2개의 DVD(디스크)에 나누어 저장되어 있습니다. 각 패키지 간에는 의존 관계가 있어서, 어떤 패키지를 설치하려면 그 패키지의 모든 선행 패키지들이 먼저 설치되어 있어야 합니다.

우리는 의존 관계를 만족하면서 단일 DVD 드라이브에서 DVD를 교체하는 횟수를 최소화하여 모든 패키지를 설치하는 순서를 찾고자 합니다.
1번 디스크에는 $1$번부터 $N_1$번까지의 패키지가 들어있고, 2번 디스크에는 $N_1 + 1$번부터 $N_1 + N_2$번까지의 패키지가 들어있습니다.
처음으로 드라이브에 디스크를 넣는 행위도 교체(삽입) 횟수 1회로 간주합니다. 디스크를 번갈아 바꾸어 가며 패키지를 설치할 때, 필요한 최소 디스크 교체 횟수를 구하는 프로그램을 작성하십시오.

[제약 조건]
• $1 \le N_1, N_2 \le 50,000$
• $1 \le D \le 100,000$ (의존성 관계의 수)
• $1 \le x, y \le N_1 + N_2$
• 입력의 마지막은 0 0 0으로 주어집니다.

입력은 여러 개의 테스트 케이스로 구성됩니다.
각 테스트 케이스의 첫째 줄에는 세 정수 $N_1, N_2, D$가 공백으로 구분되어 주어집니다.
다음 $D$개의 줄에 걸쳐 두 정수 $x, y$가 공백으로 구분되어 주어집니다. 이는 패키지 $x$가 패키지 $y$보다 먼저 설치되어야 함을 나타냅니다.
입력의 마지막 줄에는 0 0 0이 주어집니다.

각 테스트 케이스마다 모든 패키지를 설치하는 데 필요한 최소 디스크 교체 횟수를 한 줄에 하나씩 출력합니다.

3 3 2
1 4
4 2
0 0 0

3