Alien’s Necklace
發布時間: May 30, 2017, 10:21 a.m. 最後更新時間: Sept. 20, 2023, 12:50 p.m. 時間限制: 1000ms 記憶體限制: 128M
JYY is taking a trip to Mars. To get accepted by the Martians, he decided tomake a magic necklace for their king. (Otherwise, JYY will be eaten) Now, hehas collected many magic balls, and he is going to string them up. Unfortunately, only particular pairs of balls can be adjacent in thenecklace, otherwise they will explode. Notice that the first and the last ballin the necklace are also adjacent. Besides, the Martians think even numbersare unlucky, so the number of balls in the necklace must be odd. (Of courseeach ball can be used only once) A necklace contains at least 3 balls. Because the balls are really precious,JYY wants the necklace has as few balls as possible. (Then he can give restballs to his GF) So JYY wonders the number of balls he has to use to make this necklace
The input consists of several test cases. There is a single number above all,
the number of cases. There are no more than 20 cases.
For each input, the first line contains 2 numbers N and M, N is the number
of balls JYY collected, and M is the pairs of compatible balls. Balls are
numbered from 1 to N. Followed M lines, each contains 2 numbers A and B,
means that ball A and ball B are compatible. For each case, 0 < N ≤ 1,000, 0 <
M ≤ 20,000.
If the gift can't be done, just print “Poor JYY.” in a line, otherwise, print
the minimal number of balls in the necklace. Use the format in the example.
2 5 6 1 2 2 4 1 3 3 5 4 3 4 5 2 1 1 2
Case 1: JYY has to use 3 balls. Case 2: Poor JYY.
