All Discs Considered

운영체제는 여러 패키지로 이루어진 커다란 소프트웨어이며, 보통 여러 개의 매체(예: 디스크)에 나누어 배포됩니다. 예전에는 즐겨 쓰던 운영체제가 플로피 디스크 21장에 담겨 오기도 했고, 몇 년 뒤에는 CD 6장에 담겨 오기도 했습니다. 요즘은 각각 수만 개의 패키지를 담은 여러 장의 DVD로 배포됩니다.

어떤 패키지를 설치하려면 다른 패키지가 먼저 설치되어 있어야 하는 경우가 있습니다. 따라서 패키지가 매체에 잘못 배치되어 있으면, 읽기 장치가 하나(DVD-ROM 드라이브 한 대)뿐일 때 전체 시스템을 설치하는 데 매체를 여러 번 갈아 끼워야 합니다. 설치는 어딘가에서 시작해야 하므로, 다른 어떤 패키지도 먼저 필요로 하지 않고 바로 설치할 수 있는 패키지가 항상 하나 이상 존재합니다.

패키지가 매체에 어떻게 배치되어 있는지와 패키지 사이의 의존 관계 목록이 주어질 때, 모든 패키지를 설치하는 데 필요한 매체 교체 횟수의 최솟값을 구하세요. 편의상 운영체제는 정확히 $2$장의 DVD로 배포된다고 가정합니다.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스는 세 정수 $N_1$, $N_2$, $D$로 시작하며, $1 \le N_1, N_2 \le 50000$이고 $0 \le D \le 100000$입니다. 첫 번째 DVD에는 $1, 2, \ldots, N_1$번으로 번호가 매겨진 $N_1$개의 패키지가 들어 있습니다. 두 번째 DVD에는 $N_1+1, N_1+2, \ldots, N_1+N_2$번으로 번호가 매겨진 $N_2$개의 패키지가 들어 있습니다.

이어서 $D$개의 의존 관계가 주어지며, 각 관계는 두 정수 $x_i$, $y_i$ ($1 \le x_i, y_i \le N_1+N_2$)로 이루어집니다. 이는 패키지 $x_i$를 설치하려면 패키지 $y_i$가 먼저 설치되어 있어야 함을 뜻합니다. 순환 의존 관계는 없다고 가정해도 좋습니다.

마지막 테스트 케이스 다음에는 세 개의 $0$이 적힌 줄이 오며, 이 줄은 처리하지 않습니다.

각 테스트 케이스마다 모든 패키지를 설치하는 데 필요한 DVD 교체 횟수의 최솟값을 한 줄에 하나씩 출력하세요.

설치를 시작하기 전에는 드라이브가 비어 있으며, 처음으로 디스크를 넣는 것도 한 번의 교체로 셉니다. 마찬가지로 설치가 끝난 뒤 마지막 디스크를 빼서 드라이브를 비우는 것도 한 번의 교체로 셉니다.