Contest Area

shajia Criterion 2021 Round 13
Limits 1s, 512 MB

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 NN (1N1051\leq N \leq10^5) and MM (1M1061\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 uu and vv (0u,vN10 \leq u,v \le N - 1), indicating their is a direct path between rooms uu and vv.

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

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

For simplicity, the participant at the ithi’th room will be identified as participant ii.

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

InputOutput
2 2
0 1
1 0
1
0 1
Legal


Submit

Login to submit.

Statistics

83% Solution Ratio
MustangEarliest, Apr '21
prodip_bsmrstuFastest, 0.1s
RobinHood3082Lightest, 12 MB
NirjhorShortest, 737B
Toph uses cookies. By continuing you agree to our Cookie Policy.