Description

As there are many singles in Zhejiang University of Technology(ZJUT), so lily’s marriage bureau comes with the tide of fashion. On the first day, N (2<=N<=100,000) singles come to sign up at lily’s marriage bureau, they are numbered from 1 to N. Lily has to introduce any two of them to each other. Suppose they are not gayness, as boys can only be introduced to girls, girls can only be introduced to boys respectively. Lily arranges M (1<=M<=1,000,000) pairs of them. As girls are not as many as in ZJUT, so lily wants you to help him to find the minimum number of girls which satisfying his arrangement.

Input

The first line of the input is the number of cases. Following every test case: Line one: two numbers N, M; Line two~M+1:every line has a pair of numbers.

Output

If the arrangement works, output the minimum number of girls, then in the next line output the number of the girls in ascending order. If there are many solutions, choose the smallest one according to the alphabetical order. Else output “lily is handsome!”.

Sample

Input

2
2 1
1 2
3 3
1 2
1 3
2 3

Output

1
1
lily is handsome!

Source: lily