测试数据来自 system/1578

描述

John住在Alaska, 他要渡过一条很宽的河流去往一个临近的城市. John当然首先驾驶狗拉的雪橇来到河边,当然也拖来一条有三个座位的小船;随后他把船放进水中,设法将自己和所有的狗都摆渡到对岸.不过这件事远非想象中那么简单:因为有些狗相互之间有敌意,如果主人不在,它们很容易打起来,于是这些狗是不能同时留在同一侧河岸的.幸好John很了解他的狗,知道哪些狗之间是有敌意的.
有一天John带了5条狗出门: Hurricane, Bear, Wonder, Angry one, 和Argot. Bear 对Hurricane, Angry one, 以及Argot都有敌意. Wonder 则不能与Hurricane 和Angry one和睦相处. 其它的狗都能相安无事.于是这条船足够John把所有的狗平安运到对岸(注意到一条狗在船上占据一个座位),而且他在河里摆渡的次数最少是7次.他是这么干的:
带Bear和Wonder过河;
把Wonder留在对岸,带Bear回来;
带Argot和Bear过河;
带Bear和Wonder返回;
带Angry one 和Hurricane过河;
独自返回;
最后带Bear和Wonder 过河.
这样,当John不在的时候,没有两条敌对的狗同时在同一侧河岸. 而如果Argot和Hurricane也相互敌对的话, John就没办法把狗都运到对岸了.
然而John家里养了不只这么多的狗,要是下回再多带些,他可能就得花上一整天来考虑如何渡河.为了节约时间,John找到了你,请你写一个程序,对给定数量的狗和它们相互之间的敌对关系,以及船上的座位数,确定John能否把狗摆渡到对岸,如果能,则输出最少需要的步数;如果不能,输出-1.

格式

输入格式

第一行为一个整数M,表示船上的座位数;
第二行为狗的总数N(假设将狗依次编号为1…N);
第三行有一个非负整数K,表示有K对狗之间有敌意;
接下来的K行,每行有2个整数,表示互相有敌意的两条狗的编号.
M<=10,N<=10,0<=K<=50

输出格式

按照题目要求输出单个整数.

样例1

样例输入1

3
5
5
1 2
2 4
4 3
3 1
2 5

样例输出1

7

提示

显然人和每只狗都各占一个座位...