BZPRO

#3472. 穿越

内存限制：128 MiB 时间限制：10 Sec
提交 提交记录 讨论

题目描述

Applepi和Rainbow要从Nescafe星系穿越到Adera星系。为了穿越那巨大的距离，applepi发明了一种名为超时空轨道的技术。超时空轨道是双向的，连接两个星系，穿越轨道需要一天的时间。然而这个轨道只能同时给一艘飞船使用，也就是说，每条轨道每天只能有一艘飞船穿越。现在applepi要把K套模拟赛题从Nescafe运到Adera星系去，为了避免题目泄露，一艘飞船只能运一套模拟赛题。现在applepi能够到达N（N≤50）个星系，拥有M（M≤200）条超时空轨道，Nescafe星系的编号为S，Adera星系的编号为T。你需要求出至少需要几天才能将这些模拟赛题全部运到目的地。如果你不能完成这项任务，这些模拟赛日后就都会降临到你的头上！

输入格式

第一行5个整数，N,M,K,S,T。
接下来M行每行两个整数，表示一条轨道连接的两个星系编号。

输出格式

输出最少需要的天数。

样例

样例输入


			
6 7 4 1 6

1 2 

2 3

3 5

5 6

1 4

4 6

4 3

样例输出


			
4

数据范围与提示

对于100%的数据，2 <= N <= 50, 1 <= M <= 200, 1 <= K <= 50, 1 <= S, T <= N , S != T。

BZPRO Powered by Remmina.
Github Repository