동맹

아주 먼 옛날, 머나먼 은하계에 두 국가가 있었고 이 둘은 동맹을 맺기로 했다. 각 국가는 여러 개의 행성으로 이루어져 있었다. 일부 행성들은 편리한 1세대 초공간 터널로 연결되어 있었는데, 각 터널은 두 행성을 잇고 그 사이를 짧은 시간에 오갈 수 있게 해 주었다.

어느 날 과학자들이 훨씬 더 빠르게 이동할 수 있는 2세대 초공간 터널을 발견했다. 낡은 터널을 2세대 터널로 개선하는 비용은 어디서나 동일했다. 두 국가의 정치인들은 서로 다른 국가에 속한 행성들을 잇는 1세대 터널 중 일부를 2세대로 개선하여 동맹을 공고히 하기로 했다. 어느 행성도 소외되지 않도록, 상대 국가의 행성과 이어진 1세대 터널을 하나라도 가진 행성은 그중 최소한 한 개의 터널이 반드시 개선되어야 한다고 정했다. 계획을 실행에 옮겼지만 돈을 너무 많이 써서 두 국가 모두 파산했고, 동맹은 깨졌으며, 은하계에는 우주적 혼돈이 찾아왔다.

오늘날 그 사건을 연구하는 일부 역사학자들은 당시 너무 많은 터널이 개선되었으며 이 모든 혼란을 피할 수 있었다고 본다. 그들은 정치인들이 정한 조건을 만족시키기 위해 개선해야 했던 터널의 최소 개수가 얼마였는지 알고 싶어 한다. 당신의 과제는 이들을 돕는 것이다.

다음을 수행하는 프로그램을 작성하라.

• 표준 입력에서 1세대 터널망의 정보를 읽고,
• 정치인들이 정한 조건을 만족시키기 위해 개선해야 했던 터널의 최소 개수를 구하고,
• 그 결과를 표준 출력에 쓴다.

첫째 줄에 두 정수 $m$과 $n$이 공백 하나로 구분되어 주어진다. 각각 첫 번째 국가와 두 번째 국가의 행성 수를 나타내며, $1 \le m, n \le 2000$이다. 첫 번째 국가의 행성은 $1$부터 $m$까지의 정수로, 두 번째 국가의 행성은 $m+1$부터 $m+n$까지의 정수로 번호가 매겨져 있다고 하자. 둘째 줄에는 정수 $k$가 주어지며, $1 \le k \le 10000$이다. 이는 1세대 터널의 개수이다. 이어지는 $k$개의 줄에는 각 터널의 정보가 주어진다. 각 줄은 터널 하나를 나타내며, 공백 하나로 구분된 두 정수 $a$, $b$로 이루어져 있다. 여기서 $a$와 $b$는 그 터널이 잇는 두 행성의 번호이다. 어떤 터널도 한 행성을 자기 자신과 잇지 않으며, 어떤 두 행성도 여러 개의 터널로 연결되어 있지 않다고 가정한다.

처음이자 유일한 줄에, 개선해야 했던 터널의 최소 개수를 나타내는 정수 하나를 출력한다.