1028 - Game on the graph

Time Limit : 1 Second

Memory Limit : 128 MB

Submission: 18

Solved: 1

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.
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.
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
© 2015 HUST ACMICPC TEAM. All Right Reserved.