Contest Area

Dr. Wu has organized a programming contest and invited teams to participate. As It is a long contest and a good number of teams will join, Wu has set up a big building that will be used for the contest venue. The contest venue has some rooms in it. The rooms are connected with some one directional pathway. Wu always loves to try something new, and this contest was no different.

It is a team contest and each team may have different number of participants. Dr Wu has allocated a room for each of the participants. The participants of same team can communicate during contest physically but not virtually. For communication purpose, participants one one team have the permission to go to each others room. But two participants of different team cannot meet during contest time.

As it is a must to maintain the contest policy, it has to be made sure that,  different team members will not meet during contest time, even if there exist a pathway that connects two participants from different teams. If it happens, the teams who will communicate, will be banned from the contest once and for all. During contest time, the organizer will keep track which contestants meet.

It is certain that, each member of a team will have at least one path to each of it's other members. There may have path between the rooms of different team members. But two members will be considered in the same team if both of them can visit each other’s rooms.

After the contest, the organizers have submitted a list of pairs, indicating the participants who have communicated with each other. Each line of the list will be in the form a b, where participants a and b have communicated according to the organizers.

In this problem, you will have to identify whether there were any unfair communication during the contest. There may have been some errors in the data provided by the organizers, you will have to identify them as well.

Input

The first line of the input will contain two integers $N$ ($1\leq N \leq10^5$) and $M$ ($1\leq M \leq10^6$), the number of rooms and the number of direct paths between the rooms respectively.

The next M lines will have two integers $u$ and $v$ ($0 \leq u,v \le N - 1$), indicating their is a direct path between rooms $u$ and $v$.

The next line will have an integer $L$ ($1 \leq L \leq10^5$), indicating the size of the list prepared by the organizers.

The next L lines will have two integers $a$ and $b$ ($0 \leq a,b \leq N-1$), indicating a communication spotted by the organizers between the participants $a$ and $b$.

For simplicity, the participant at the $i’th$ room will be identified as participant $i$.

Output

For each communication a b, if participant a and participant b are from same team and have a communication during contest, print “Legal” (without quotes). If they are not from the same team and have communication during contest, print “Illegal” without quotes.

Sample

2 2
0 1
1 0
1
0 1

Legal