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?

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.

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