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

      话说puga来到了神秘岛。他发现,这是一个由n个小岛和一个中心岛组成的群岛,群岛之间有m座桥。令他感到惊讶的是,这些桥并不是固定不变的,经较长时间的观察,发现它们会随时间作周期性的变化(即桥的两端会不断更换)。
      puga用望远镜看到到远远的那个中心岛上有一间小屋,架在一棵好大好大的树上。于是他决定前往中心岛上的那间空中楼阁。puga当然希望越早到越好,那么,你能帮帮他们吗?
    为方便计算,puga把小岛按1..n编号,0表示中心岛。puga一开始在编号为1的小岛上。在岛上行走的时间忽略不计,过桥的时间为1个单位。岛上的桥变化的周期为T,在nT+i(n=0,1,2,…;i=1,2,…,T)时刻岛上的桥为第i种状态,一开始的时刻为1。两个小岛间可能有多条桥相连。在任一时刻,puga可以选择过桥,也可以原地不动。当然,如果无桥可过,puga只能在原地等待。

    输入格式

      第一行包括三个整数n(1<=n<=80),m(1<=m<=10000)和T(1<=T<=10),分别表示小岛的个数,岛上桥的数量和桥改变的周期T。
    接下来分别描述第1..T种状态,每种状态有m行,每行有两个整数a, b(0<=a,b<=n),表示这种状态时小岛a和b有一条桥相连。两状态之间用一空行隔开。

    输出格式

    仅有一个整数,表示puga最少得花多少时间到达中心岛。如果puga无法到达中心岛,则输出“Poor puga!”。

    样例输入

    【输入样例1】
    4 5 2
    1 2
    1 3
    1 4
    2 0
    4 0

    1 3
    1 3
    2 3
    4 3
    3 0
    【输入样例2】
    7 3 2
    1 2
    1 4
    6 0

    2 5
    3 6
    4 7

    样例输出

    【输出样例1】2
    【输出样例2】Poor puga!

    提示

    1<=n<=80,1<=m<=10000,1<=T<=10