1028 - Game on the graph

Time Limit: 1s Memory Limit: 128MB

Submissions: 18 Solved: 1
Description
Liruqi and Isun are playing a game on an undirected graph. Rules are like this: 1) Two players take turns to break an edge that is still connected(directly or indirectly) to the orignal(node 1). 2) The player who got no edge to break lose the game. 3) Liruqi goes first(He always does this~). Now given an undirected graph with N nodes, numbered from 1 to N. Assume that both of the two excellent coders use the best strategy, you are to tell us who will win the game.
Input
fist line: two integer N(1<=N<=100), M(1<=M<=10000), indicate the number of nodes and number of edges in the graph. line 2 to M+1: each line contains two integer ui, vi, indicate a edge connecting node ui and vi. Note that multiple edges may exist.
Output
Print one line: the name of the player who will win the game("Liruqi" or "Isun").
Sample Input
3 3
1 2
2 3
1 3
Sample Output
Liruqi
Hint
Source
liruqi