• [I] I Want You

  • 时间限制: 1000 ms 内存限制: 65535 K
  • 问题描述
  • In the eyes of XP, EG is the most beautiful girl in the world. This day he was courage enough to say love to EG. But the nauty EG said "Close your eyes and I will hide myself. if you can find out me , I will accept your request". Obviously XP is very happy. He knew EG is stupid. and he can easy to find out her .because they had did this game many many times. She always hide herself in a building with a lot of rooms. These rooms are numbered 1,2...k. Each room has two doors except the k-th(last) room, and if you want to enter the i-th room, you must in room i-1; XP knew EG must be in the last room. When XP prepare to enter the building , he found every door were locked by two locks. The door will be opened if you have either key to the locks. The keys were kept by BA(the building administrator). But BA is a little strange. He arranged two keys into one group. And you can only get either of the two keys from BA. So XP get one key of each group. Of course he may not take. Now, can XP get into the last room and find EG out? Please help the poor XP.


  • 输入
  • There are several test cases. Every test case starts with a line containing two positive integers N (1 <= N <= 210) and M (1 <= M <= 211) separated by a space, the first integer represents the number of pairs of keys and the second integer represents the number of doors. The 2N keys are numbered 0, 1, 2, ..., 2N - 1. Each of the following N lines contains two different integers, which are the numbers of two keys in a pair. After that, each of the following M lines contains two integers, which are the numbers of two keys corresponding to the two locks in a door.
  • 输出
  • If XP can find out EG, print the keys XP shuld take by the ascending order (you can sure there is only one way.) or print "oh,poor XP will be single the whole life."
    More details see the output?
  • 样例输入
  • 3 6
    0 3
    1 2
    4 5
    0 1
    0 2
    4 1
    4 2
    3 5
    2 2
    
    2 3
    0 3
    1 2
    1 2
    0 0
    3 1
  • 样例输出
  • oh,poor XP will be single the whole life.
    
    0 1
  • 提示
  • 来源
  • 加多宝凉茶
  • 操作

显示春菜