The princess bride P34606


pdf   zip

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 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 xy. Assume 3 ≤ n ≤ 1000 and that all the roads are different. Villages are numbered starting at 1.


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


    true love
  • Information
    Salvador Roura
    Official solutions
    User solutions