2017 Multi-University Training Contest - Team 9 1005&&HDU 6165 FFF at Valentine【強聯通縮點+拓撲排序】FFF at Valentine

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 1060    Accepted Submission(s): 506

Problem Description

At

Valentine's eve, Shylock and Lucar were enjoying their time as any

other couples. Suddenly, LSH, Boss of FFF Group caught both of them, and

locked them into two separate cells of the jail randomly. But as the

saying goes: There is always a way out , the lovers made a bet with LSH:

if either of them can reach the cell of the other one, then LSH has to

let them go.

The jail is formed of several cells and each cell has

some special portals connect to a specific cell. One can be transported

to the connected cell by the portal, but be transported back is

impossible. There will not be a portal connecting a cell and itself, and

since the cost of a portal is pretty expensive, LSH would not tolerate

the fact that two portals connect exactly the same two cells.

As an

enthusiastic person of the FFF group, YOU are quit curious about whether

the lovers can survive or not. So you get a map of the jail and decide

to figure it out.

Input

∙Input starts with an integer T (T≤120), denoting the number of test cases.

∙For each case,

First line is two number n and m, the total number of cells and portals in the jail.(2≤n≤1000,m≤6000)

Then next m lines each contains two integer u and v, which indicates a portal from u to v.

Output

If the couple can survive, print “I love you my love and our love save us!”

Otherwise, print “Light my fire!”

Sample Input

Sample Output

Source

<a href="http://acm.hdu.edu.cn/search.php?field=problem&amp;key=2017+Multi-University+Training+Contest+-+Team+9&amp;source=1&amp;searchmode=source">2017 Multi-University Training Contest - Team 9</a>

分析：縮點為DAG，則如果在拓撲序中出現了有兩個及以上入度為0的點則不合法

下面給出AC代碼：