잉크 섞기

잉크 병이 $n$ 개 있고, 1부터 $n$까지 번호가 매겨져 있다. 처음에는 모든 병이 비어 있다. 처음 $m$ 개의 병에는 서로 다른 색의 잉크 $m$ 가지가 담기며, 나머지를 포함한 $n$ 개의 병은 호스로 서로 잉크를 주고받을 수 있다. 잉크가 계속 흘러들어 섞이면서 병의 색은 바뀔 수 있지만, 하루가 끝나면 색은 평형에 도달하여 더 이상 바뀌지 않는다. 평형 상태에서는 다음 성질이 성립한다.

• 병 A에 잉크가 있는 것은, 처음 $m$ 개의 병에 담긴 잉크가 여러 호스를 거쳐 A까지 흘러갈 수 있는 경우뿐이다. 그렇지 않으면 A는 비어 있다.
• 비어 있지 않은 병에는 한 가지 색의 잉크만 들어 있다.
• 병 B에 여러 잉크 공급원이 연결되어 있고 (처음 $m$ 개의 병에 넣은 서로 다른 $m$ 가지 색의 잉크이거나, 호스로 연결된 비어 있지 않은 병의 잉크), 공급원의 잉크 색이 모두 같지 않으면 B를 "mixer"라고 부른다.
• 비어 있지 않으면서 mixer가 아닌 병은, 공급원에 들어 있는 것과 같은 색의 잉크를 담고 있다.
• mixer 병은 처음 $m$ 개의 병에 넣은 잉크와 다른, 완전히 새로운 색의 잉크를 담는다. 또한 서로 다른 mixer 병은 서로 다른 색의 잉크를 담는다.

예를 들어 아래 그림은 평형 상태에 있는 잉크 병 4개를 보여 준다. 1번과 2번 병에는 각각 빨간색과 파란색 잉크가 들어 있다. 1번 병의 잉크는 3번 병으로, 2번 병의 잉크는 3번과 4번 병으로 흘러간다. 1번과 2번 병은 각각 빨간색과 파란색 잉크를 담고 있다. 3번 병은 서로 다른 색인 빨간색과 파란색을 공급받으므로 mixer이며, 빨간색과 파란색이 섞인 새로운 색(보라색이라고 하자)의 잉크를 담는다. 4번 병은 파란색 잉크를 담고 있다. 전체적으로 빨간색, 파란색, 보라색 세 가지 색이 있으며, 이것이 최소이다.

다음 그림에서도 1번과 2번 병에 각각 빨간색과 파란색 잉크를 넣는다. 이 잉크는 3번과 4번 병으로 흘러간다. 3번 병에서는 앞의 예와 같이 파란색과 빨간색 잉크가 섞여 새로운 색(보라색)이 된다. 4번 병에도 3번 병과 같은 파란색과 빨간색 잉크가 들어가지만, 3번과 4번은 서로 다른 mixer이므로 결과 색(바이올렛이라고 하자)은 3번 병의 색과 다르다. 전체적으로 빨간색, 파란색, 보라색, 바이올렛 네 가지 색이 있으며, 이것이 최소이다.

처음 $m$ 개의 병은 서로 잉크를 주고받을 수도 있다. 마지막 그림에서 1번과 2번 병에는 각각 빨간색과 파란색 잉크를 넣지만, 두 병은 서로에게 잉크를 보낸다. 1번 병의 잉크는 3번 병으로, 3번 병의 잉크는 4번 병으로 흘러가며, 4번 병의 잉크는 자기 자신에게 흘러간다. 1번과 2번 병은 보라색과 바이올렛이라는 서로 다른 색의 잉크를 만드는 mixer이다. 3번 병은 1번 병에서만 잉크를 공급받으므로 3번 병의 색은 1번 병의 색과 같다. 4번 병은 두 가지 잉크를 받지만 색이 같으므로 mixer가 아니며 결과 색도 같다. 전체적으로 보라색과 바이올렛 두 가지 색이 있으며, 이것이 최소이다.

병들의 구성이 주어지면, 평형 상태에서 병에 들어 있는 서로 다른 잉크 색의 최소 개수를 출력하는 프로그램을 작성하라. 빈 병이 있을 수 있지만, 빈 병은 세지 않는다.

첫 줄에 세 정수 $n$, $m$, $k$ ($1 \le m \le n \le 100{,}000$, $1 \le k \le 500{,}000$)가 주어진다. $n$은 잉크 병의 개수, $m$은 고유한 잉크가 담기는 병의 개수, $k$는 호스의 개수이다. 병은 1부터 $n$까지 번호가 매겨져 있다. 다음 $k$개의 줄 중 $i$번째 줄에는 두 개의 0 이상 정수 $f_i$, $t_i$가 주어지며, 이는 $i$번째 호스가 $f_i$번 병의 잉크를 $t_i$번 병으로 보낸다는 뜻이다. 같은 쌍의 병을 여러 호스가 연결할 수 있다.

한 줄만 출력한다. 그 줄에는 평형 상태에서 병에 들어 있는 서로 다른 잉크 색의 최소 개수를 쓴다.