Plug It In!

아담은 새 아파트로 이사하면서 짐을 아무렇게나 배치했다. 전자제품마다 콘센트를 하나씩 따로 쓸 수 있도록 배치하지는 않았다.

기기의 전선 길이에는 한계가 있어서, 기기를 옮기지 않으면 일부 콘센트에만 꽂을 수 있다. 아담은 아무것도 옮기지 않고 가능한 한 많은 기기를 바로 사용하고 싶다. 멀티탭은 콘센트 하나를 세 개로 바꾼다. 전선이 없어서 콘센트에 꽂으면 그 콘센트가 세 배가 된다.

입력은 세 정수 $m$, $n$, $k$가 한 줄에 주어진다. 여기서 $m$ (1 ≤ $m$ ≤ 1500)은 콘센트의 개수, $n$ (1 ≤ $n$ ≤ 1500)은 전자기기의 개수, $k$ (0 ≤ $k$ ≤ 75000)은 가능한 연결의 개수이다.

이후 $k$개의 줄에 정수 $x_i$와 $y_i$가 주어지며, 이는 콘센트 $x_i$로 기기 $y_i$에 전원을 공급할 수 있다는 뜻이다. 콘센트와 기기는 1번부터 번호가 매겨진다.

아담이 전원을 공급할 수 있는 기기의 총 개수를 한 줄에 출력한다.