会议安排

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

一个重要的会议由A公司的M位代表和B公司的N位代表参加(M,N不大于1000,代表用1,2,…,M和1,2,…N表示)。他们被预先分成K组进行谈判。每组两个人分别来自A公司和B公司。每个参加会议的代表都至少参加了一组谈判。会议为每一个代表都准备了一个房间。技术人员将会在一些房间之间连上直通电话,一个代表至少要和他的一个谈判对手直接联络。连接一个直通电话的价格是常数。技术人员要用尽量少的花费满足会议的要求。

Input

第1行是三个用空格隔开的整数M,N和K。下面的K行每行有一对数P1和P2,P1表示A公司的代表,P2表示B公司的代表。P1和P2之间用空格隔开。

Output

输出只有一行,即最少要装的电话的数目。

Sample Input

3 2 4
1 1
2 1
3 1
3 2

Sample Output

3

Hint

 

Source