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.