TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3666
  • 题目
  • P3666渡河
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    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

    输出格式

    按照题目要求输出单个整数,表示最少步数

    样例输入

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

    样例输出

    7


    来源  改编自12th Latvian olympiad in informatics Šķērsojot upi