题目描述

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 杯冬令营模拟赛