ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1630. Talisman

Time limit: 1.0 second
Memory limit: 64 MB
Having surveyed his worktable once again, Petya suddenly understood the cause of all his recent failures: of course, the talisman! His usual talisman, the pink pig, apparently couldn't help him in the contest. Petya pondered over this problem and came out with a set of conditions for a new talisman:
  1. The talisman must be a structure consisting of identical balls with a radius of 1 mm in 3-dimensional space; some of the balls must be connected by 8 mm long rods.
  2. If two balls are connected by a chain of rods, then the minimal number of rods in a chain connecting these balls must be equal to the distance in centimeters between the centers of the balls.
Petya has developed a scheme describing the number of balls in his future talisman and the pairs of balls that must be connected by rods. Now he wants to write a program that will find if it is possible to construct a talisman according to this scheme. However, as Petya still doesn't have a proper talisman, he can't produce a working program. That is why Petya asks for your help.


The first line contains the number of balls N and the number of rods M in Petya's scheme (1 ≤ N ≤ 100; 0 ≤ M ≤ 10000). In the following M lines, pairs of balls connected by rods are given. The balls are numbered from 1 to N. For any two balls in the scheme, there is at most one rod connecting them; no ball is connected by a rod with itself.


If it is possible to construct a talisman by Petya's scheme, output “Luck is possible”; otherwise, output “Unlucky Petr”.


3 3
1 2
1 3
2 3
Luck is possible
4 4
1 2
1 3
1 4
2 3
Unlucky Petr
Problem Author: Sergey Pupyrev (prepared by Daniil Ayzenshteyn)
Problem Source: XIII Open USU Championship