Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Contest Area

By shajia · 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


    Discussion

    Statistics


    82% Solution Ratio

    MustangEarliest, 2w ago

    prodip_bsmrstuFastest, 0.1s

    RobinHood3082Lightest, 12 MB

    NirjhorShortest, 737B

    Submit

    Login to submit

    Editorial

    First of all let's look into the important part of the problem. We will find that the room is connec...

    Related Contests