스키 경로 감시

맑은 날 내린 새 눈은 스키 타기에 더없이 좋다. 열정적인 스키어들은 완벽한 설질을 즐기기 위해 로키산맥의 큰 산에 몰려든다. 산에 오르는 방법은 헬리콥터뿐이고, 스키어들은 뛰어내려 산을 타고 내려간다.

이 과정은 다소 혼란스러울 수 있어 몇 가지 규정을 두고 있다. 스키어는 정해진 지점인 교차점에서만 산에 들어오거나 나갈 수 있다. 산에 있는 동안에는 지정된 스키 경로로만 이동할 수 있으며, 각 경로는 한 교차점에서 시작해 더 낮은 곳의 다른 교차점에서 끝난다. 같은 교차점에서 시작하는 스키 경로가 여러 개 있을 수 있지만, 스키어끼리 충돌하지 않도록 두 스키 경로가 같은 교차점에서 끝나는 경우는 없다.

마지막으로 모든 스키어는 하루 전에 헬리콥터 서비스에 스키 계획을 등록해야 한다. 스키 계획에는 그들이 타고 올라갈 교차점과 산 아래에서 픽업받을 교차점이 명시된다. 스키어가 산에 나타나면 반드시 계획을 따라야 하지만, 일부 스키어는 몸이 아파 아예 나타나지 않는다.

당신의 임무는 스키 계획을 검토하고 일부 교차점에 감시 장비를 설치해 실제로 나타난 스키어가 몇 명인지 세는 것이다. 운영 비용을 최대한 낮추기 위해, 각 스키어가 감시되는 교차점을 적어도 하나 지나도록 하는 데 필요한 감시 교차점의 최소 개수를 구해야 한다.

그림 I.1: 첫 번째 예제 입력의 그림.

그림 I.1은 첫 번째 예제 입력을 보여준다. 점선은 스키어들이 등록한 다섯 가지 계획을 나타낸다. 교차점 5, 9, 10을 감시하면 모든 계획이 감시되는 교차점을 적어도 하나 포함하게 할 수 있다. 더 적은 수의 교차점을 감시하면 일부 스키어를 놓치게 된다.

입력의 첫 줄에는 세 정수 n, k, m이 주어지며, n (2 ≤ n ≤ 250 000)은 교차점의 수, k (1 ≤ k < n)는 스키 경로의 수, m (1 ≤ m ≤ 250 000)은 계획의 수이다.

이어서 k개의 줄이 주어지고, 각 줄에는 두 정수 1 ≤ u, v ≤ n이 있으며, 이는 교차점 u에서 시작해 교차점 v에서 끝나는 스키 경로가 있음을 나타낸다.

이어서 m개의 줄이 주어지고, 각 줄에는 서로 다른 두 정수 1 ≤ s, t ≤ n이 있다. 각 줄은 한 스키어가 교차점 s에 착륙해 교차점 t까지 산을 타고 내려갈 계획임을 나타낸다. 스키 경로를 따라 교차점 s에서 교차점 t에 도달할 수 있고, 교차점 t가 산의 아래쪽(즉, t에서 시작하는 스키 경로가 없음)임이 보장된다. (s, t) 쌍은 두 번 이상 나타나지 않는다.

각 스키 계획이 감시되는 교차점을 적어도 하나 포함하도록 하는 데 필요한 감시 교차점의 최소 개수를 출력한다.