2013年7月7日 星期日

10543 - Traveling Politician


Problem E
Traveling Politician
Time Limit: 2 seconds

一位來自  Alliance of Conservative Monarchists (ACM) 的政治家將成為下一次選舉的候選人,為了確保他能勝選,他將會舉行至少 k (≧ k)場公開演講。他將會在每一天都舉行演講,但不會連續兩天都在同一個城市中舉行演說,因為這麼做是徒勞無用的。然而,這位政治家相信間隔一天之後的演講是有用的,例如他在星期一演講過,而星期三他也許會在同一個城市中演講,人們將會忘記他第一次演講的內容,而第二次的演講就會更有效用。

他非常堅信會贏得這場勝利,因此他將會移動到首都。他的第一場演講來自於他的家鄉,而最後一場演講將會在首都。演講太多次將會使他疲累,因此不希望舉行太多場,但至少舉行 k 場以贏得勝利。

找一個最少的演講次數,從起點家鄉到終點首都至少舉行 k 場演講 (包括在家鄉跟首都的演講),同時也不會存在連續兩天在同一個城市演講。

Input
輸入將會包含少數幾筆冊資,每組測資將會有 3 個整數,分別是 n, m, k 代表接下來有 n 個城市、m 條道路及舉行至少 k 場演講。接下來會有 m 行,每行會有 2 個整數 u, v,表示政治家可從城市 u 抵達城市 v (需要一天的時間),而其他的路線因為他的經費不夠無法使用。而起點家鄉編號 0,終點首都編號 n-1。
 2<=n<=50, 2<=k<=16

最後一行以包含兩個 0 結束程序

Output
對於每組測資輸出一行最少的演講個數,如果沒辦法則輸出 "LOSER"。
如果舉行大於 20 場,同樣也輸出 "LOSER"。

Sample Input Sample Output
3 3 3
0 1
0 2
1 2
5 6 5
0 1
0 3
1 2
2 4
3 2
3 4
3 3 10
0 1
1 0
1 2
0 0 0
3
LOSER
11

Problemsetter: Igor Naverniouk, special thanks to Shahriar Manzoor