Description

约翰有 N 只编号为1到 N 的牛和 K 个依次排成一行的草场.每天清晨，牛们按标号的顺序排好队，前往草场活动.当牛的队列经过第一个草场，约翰会把前N1只牛留在这里，其余的牛继续前进.当牛的队列经过第二个草场，约翰会把前N2只牛留在这里，其余的牛继续前进.如此直到所有牛都进入草场.而且，牛一旦进入草场，一天都将待在这里，不会到别的草场去.

牛们都非常珍视友情，每只牛都有一些希望一起活动的朋友.我们用一个无序数对(i, j)，表示牛环口牛 j 是一对朋友(i<>j).如果她们能待在一个草场，那约翰就满足了牛友们的一个愿望.输入的时候，如果(i, j)出现了，那保证(j，i)不会再出现.

现给你所有的牛友清单，请制定一个方案，让约翰满足尽量多的牛友的愿望.约翰坚持，不能有一个草场是空的，也不能有一个草场只有一只牛活动(这样她会觉得孤单).

Format

Input

第1行输入三个整数 N,K,F(4<=2*K<=N<=150,1<=F<=200).接下来 F 行，每行用一对整数表示一对牛友.

Output

输出最大的满足的愿望数.

Samples

5 2 4
1 2
2 3
4 5
1 5

3