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

USU Championship 2008

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. 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.

Input

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.

Output

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

Samples

inputoutput
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
To submit the solution for this problem go to the Problem set: 1630. Talisman