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:
- 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.
- 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
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”.
Luck is possible
Problem Author: Sergey Pupyrev (prepared by Daniil Ayzenshteyn)
Problem Source: XIII Open USU Championship