分糖果

题目描述

无向朋友关系图中，编号c的小朋友在第1秒持有糖。收到糖的小朋友同时向所有尚未收到的邻居传糖，每条关系传播需1秒；本人从收到糖起再用m秒吃完。求所有人都吃完的最早秒数。

输入

第一行n,p,c，1≤n≤100000，0≤p≤min(200000,n(n-1)/2)，1≤c≤n；第二行m，0≤m≤10^9；随后p行互不重复的不同端点无向关系。

输出

若有人无法收到糖，输出-1；否则输出最后吃完的秒数。

输入样例

4 3 1
2
1 2
2 3
1 4

输出样例

5