기숙사 파티

평범한 기숙사에서는 두 학생이 한 방을 함께 쓴다. 신입생 잭과 파티를 좋아하는 주드가 한 방을 쓰게 되었다. 어느 날 주드는 방에서 파티를 열자는 생각을 떠올린다. 반면 잭은 조용한 것을 좋아하는데, 기숙사에서는 이미 조용함을 찾기가 어렵다. 게다가 주드에게는 친구가 아주 많아서, 18 m² 남짓한 방에서 파티가 열린다는 생각만 해도 잭은 몸서리가 난다.

주드는 여학생 $N$명과 남학생 $M$명을 파티에 초대하려 한다. 각 여학생은 (비어 있을 수도 있는) 어떤 남학생 집합에 관심이 있고, 그 남학생들도 똑같이 그 여학생에게 관심이 있다(관심은 항상 서로 간의 것이다). 파티를 더 활기차게 만들기 위해 주드는 되도록 많은 손님이 춤을 추도록 짝을 지어 주고 싶다. 단, 서로에게 관심이 있는 두 사람만 한 짝이 되어 춤을 출 수 있다.

잭은 파티가 성공해서 주드가 파티를 더 자주 열게 될까 봐 걱정이다. 파티의 성공 여부는 소음의 크기로 판단된다는 것은 잘 알려져 있다. 첫째, 춤을 추는 손님은 추지 않는 손님보다 시끄럽다. 둘째, 아직 춤을 추지 않는 두 사람이 서로에게 관심이 있다면, 그들은 저절로 새로운 짝을 이루어 춤을 추기 시작하고, (스스로 나섰다는 자부심과 약간의 취기로) 유난히 시끄럽게 군다. 잭은 이런 짝이 생기는 것을 어떻게든 피하고 싶다. 그래서 잭은 소음이 최소가 되는 짝짓기를 하려 한다. 즉, 서로에게 관심 있는 두 사람이 모두 춤을 추지 않는 경우가 하나도 없어서 새로운 짝이 저절로 생길 수 없으면서, 춤추는 짝의 수가 가능한 한 적은 짝짓기이다.

이러한 조건을 만족하는 짝짓기에서 춤추는 짝의 최소 개수 $S$를 구하여라.

첫째 줄에 여학생 수 $N$ ($1 \le N \le 19$), 남학생 수 $M$ ($1 \le M \le 19$), 서로 관심 있는 쌍의 수 $K$ ($0 \le K \le N \cdot M$)가 주어진다. 이어지는 $K$개의 줄에는 각각 두 정수 $A_i$ ($1 \le A_i \le N$)와 $B_i$ ($1 \le B_i \le M$)가 주어지며, 이는 여학생 $A_i$와 남학생 $B_i$가 서로에게 관심이 있음을 뜻한다. 같은 쌍이 두 번 이상 주어지지는 않는다.

조건을 만족하는 짝짓기 중에서 춤추는 짝의 최소 개수 $S$를 한 줄에 출력한다.