CF144D Missile Silos

A country called Berland consists of $ n $ cities, numbered with integer numbers from $ 1 $ to $ n $ . Some of them are connected by bidirectional roads. Each road has some length. There is a path from each city to any other one by these roads. According to some Super Duper Documents, Berland is protected by the Super Duper Missiles. The exact position of the Super Duper Secret Missile Silos is kept secret but Bob managed to get hold of the information. That information says that all silos are located exactly at a distance $ l $ from the capital. The capital is located in the city with number $ s $ . The documents give the formal definition: the Super Duper Secret Missile Silo is located at some place (which is either city or a point on a road) if and only if the shortest distance from this place to the capital along the roads of the country equals exactly $ l $ . Bob wants to know how many missile silos are located in Berland to sell the information then to enemy spies. Help Bob.

The first line contains three integers $ n $ , $ m $ and $ s $ ( $ 2

Print the single number — the number of Super Duper Secret Missile Silos that are located in Berland.

In the first sample the silos are located in cities $ 3 $ and $ 4 $ and on road $ (1,3) $ at a distance $ 2 $ from city $ 1 $ (correspondingly, at a distance $ 1 $ from city $ 3 $ ). In the second sample one missile silo is located right in the middle of the road $ (1,2) $ . Two more silos are on the road $ (4,5) $ at a distance $ 3 $ from city $ 4 $ in the direction to city $ 5 $ and at a distance $ 3 $ from city $ 5 $ to city $ 4 $ .