穿越

时间限制:10s      空间限制:128MB

题目描述

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。


题目来源

Adera 1 杯冬令营模拟赛

Menuappsclose