六度空间

题目描述

在数学领域的有一个神秘迷人的猜想叫做六度空间理论: 你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过五个中间人你就能够认识任何一个陌生人.

PP是北京化工大学的一只普通单身汪,他每天总是早早的起床,然后屁颠屁颠的背上自己的小书包高高兴兴的去上课.PP觉得这样的生活很幸福. 然而周围总有一些可恶的邪恶汪在PP周围秀恩爱,喂PP吃狗粮.这打击到了PP,PP很生气,决心也找一个同伴.

有一天PP在去食堂的路上,遇见了一只特别美丽的汪汪RR.PP深深地被它所吸引,但PP不认识它,又不好意思向它主动打招呼.这时PP想到了六度空间理论.想通过自己认识的汪间接认识RR.

现在有编号从1到n的n只汪,其中PP的编号为1,RR的编号为n.(2<=n<100000)

有m条认识关系,关系的表示形式为a b.表示:编号为a的汪认识编号为b的汪,与此同时编号为b的汪认识编号为a的汪(双向认识).(0<=m<100000,1<=a,b<=n且a!=b)

问PP能否最多中间通过5只汪间接认识美丽的RR,如果能输出”PP will be happy!”(没有引号),否则输出”PP will die!”(没有引号).

输入

输入只包含一组数据.

第一行一个整数n表示有n只汪

第二行有一个整数m表示有m种关系

接下来有m行每行有两个数字a b(中间用空格隔开).表示a认识b,同时b认识a

(数据建议用scanf读入)

输出

如果PP可以最多通过中间的五个人认识RR,就输出:”PP will be happy!”,

否则输出: “PP will die!”.(输出结束之后记得换行)

样例输入

6

5

1 2

1 3

1 4

2 3

5 6

样例输出

PP will die!

考察的是图的vector邻接表和搜索。