The princess bride P34606


Statement
 

pdf   zip

html
Once upon a time there was a girl called Buttercup who lived in Florin. The country had n villages and m bidirectional roads connecting them. The true love of Buttercup was a farmboy called Westley who lived in village number 1. However, Buttercup was locked in the castle of Prince Humperdinck (the bad guy of this story) in village number 2. To rescue Buttercup, Westley first had to reach the castle.

The prince wanted to prevent this by hiring outlaws to control the roads. Each road could only be controlled from any of the two villages at its ends. Each outlaw could control any road, but should be the same road all the time. Any village could accommodate as many outlaws as needed.

All the outlaws for hire lived in village number 3. Each outlaw charged one gold coin for each road that he had to traverse to reach any of the two villages at the ends of the road that Prince Humperdinck assigned under his control. What was the minimum amount of gold coins that the prince had to pay to ensure that Westley could not reach the castle?

Input

Input consists of several cases. Every case begins with n and m, followed by m pairs x y to indicate a road between x and y, where x ≠ y. Assume 3 ≤ n ≤ 1000 and that all the roads are different. Villages are numbered starting at 1.

Output

For each case, print the minimum number of coins that Prince Humperdinck had to pay to prevent the meeting of Westley and Buttercup. If this was unavoidable, print “true love”.

Public test cases

  • Input

    5 4      1 4  4 2  3 5  5 1
3 0
3 1      2 1
10 12    1 4  4 5  5 3  3 6  6 7  7 2  1 2  1 8  8 9  9 10  10 2  3 9

    Output

    2
0
true love
4
    • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++