六度空間

題目描述

在數學領域的有一個神秘迷人的猜想叫做六度空間理論: 你和任何一個陌生人之間所間隔的人不會超過六個，也就是說，最多通過五個中間人你就能夠認識任何一個陌生人.

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鄰接表和搜尋。