Problem E: 分糖果

Problem E: 分糖果

Time Limit: 2 Sec  Memory Limit: 256 MB
Submit: 6  Solved: 2
[Submit] [Status] [Web Board] [Creator:]

Description

童年的我们,将和朋友分享美好的事物作为自己的快乐。这天,C小朋友得到了糖果,将要把这些糖果分给要好的朋友们。已知糖果从一个人传给另一个人需要1秒的时间,同一个小朋友不会重复接受糖果。由于糖果足够多,如果某时刻某小朋友接受了糖果,他会将糖果分成若干份,分给哪些在他身旁且还没有得到糖果的小朋友们,而且自己会吃一些糖果。由于嘴馋,小朋友们等不及将糖果发完,会在得到糖果后边吃边发(不会牙疼吗???)。每个小朋友从接收糖果到吃完糖果需要m秒的时间。那么,如果第1秒C小朋友开始发糖,第几秒所有小朋友都吃完了糖呢?


In our childhood, sharing delicious candies with friends was our own happiness. On a specific day, child C got the candies and will distribute the candies to his best friends. It takes around 1 second for candies to pass from one person to another, and the same child will not receive candies repeatedly. Since there are enough candies, if a child accepts candies at a certain moment, he will divide the candies into several portions, and distribute them to those children who are by his side who have not yet received the candies, and will eat some candies themselves. Because of their cravings, the children can’t wait to finish sending out the candies. After receiving candies they will distribute as well as eat some at the same time (wouldn’t they have a toothache??). It takes m seconds for each child to receive the candy and to finish eating the candy. So, if in the first second, child C starts to send candy, at which point in time will all the children have finished the candy?


Input

第1行为三个整数n、p、c,为小朋友数、关系数和C小朋友的编号。(n<=100000)
第2行为一个数m,表示小朋友吃糖的时间。
下面p行每行两个整数,表示某两个小朋友在彼此身旁。


The first line is three integers n, p, c, which are the number of children, the relationship number, and the number label of child C. (n<=100000)

The second line is a number m, which represents the time for the children to eat candy.

The next p lines contain 2 integers each which represents the children that are next to one another.

 


Output

一个整数,为所有小朋友都吃完了糖的时间。


An integer, the time for all the children to eat the candy.


Sample Input Copy

4 3 1
2
1 2
2 3
1 4

Sample Output Copy

5