Students can be divided into two groups in CS203. One is “Xueba”, the other is “Xuezha”. In CS203 course, there are n students. Each student is either in “Xueba” group or “Xuezha” group. In this course, the students in the same group will never fight as they have the same interests. Now Dr. Tang has a group of fight log. Each record in the log has two integers x y, it means student x fight with student y. Please verify whether the group of record is legal. All students are labeled from 1 to n.

A group of record is legal if and only if no student is both in “Xueba” and “Xuezha” group.

The first line will be an integer T. (1 <= T <= 50) T is the number of test cases.

For each test case, the first line will be two integers n and m. ( 2 <= n <= 5000, 1 <= m <= 20000)

n is the number of students. And m is the number of log records.

Then there will be m lines. Each line will be a record: x y, it means student x fight with student y.

For each test case, print “legal” (without quotes) or “illegal”(without quotes)

For the first sample, {1, 3, 5} are good
guys, {2, 4} are bad guys. We can add 6, 7 to arbitrary group. Now everyone is
in only one group.

For the second sample, we cannot divide
them into two groups.