You are trying to purchase a car and will be visiting a number of locations N (represented as points), each labeled i(1 <= i <= N) There are M roads connecting the points together, and road j(1 <= j <= M) of length d; bidirectionally connects points u, and u.

The car comes with a fuel tank that has a capacity of Lmoving 1 unit of distance for every 1 unit of fuel it expends.

Some of the points have a gas stationg_{i} = 1 if there is a gas station at point i, and g_{i} = 0 if there is no gas station. If you reach a point with a gas station without running out of fuel you are able to fill up your car's tank. (If you run out of fuel just as you reach a point with a gas stationyou can still fill up) If you run out of gas before reaching a gas station then you have no option but to call a tow truck to transport your vehicle.

You reside at location 1, which has a gas stationYour challenge is to create a program that computes the number of locations you can visit without running out of fuel. You must also return home at the end of the journey. You are free to take whichever path you like in order to reach a destination and to refuel at any particular gas station however many times you like.