Compute Number of Locations

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_j bidirectionally connects points u_j and v_j. The car comes with a fuel tank that has a capacity of L, moving 1 unit of distance for every 1 unit of fuel it expends. Some of the points have a gas station. g_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 station, you 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 station. Your 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. Function Description Complete the function computeNumberOfLocations in the editor. computeNumberOfLocations has the following parameters:

• 1. N: an integer, the number of locations
• 2. M: an integer, the number of roads
• 3. L: an integer, the fuel tank capacity
• 4. int g[N]: an array of integers indicating the presence of gas stations
• 5. int roads[M][2]: a 2D array of integers where each element is a pair of integers representing a road Returns int: the number of locations you can visit without running out of fuel

Constraints

• 1 ≤ N, M ≤ 100000, integer
• 1 ≤ L ≤ 10⁹, integer
• g_i is 0 or 1 (1 ≤ i ≤ N) -> g_i = 1 indicates that there is a gas station at point i;;; -> g_i = 0 indicates that there is NOT a gas station at point i
• u_j ≤ v_j + 1 (1 ≤ j ≤ M - 1), integer
• 1 ≤ u_j Roads are on a straight line. put differently: M = N - 1, u_j = j, v_j = j + 1 (1 The only gas station is located at point 1. g_2 = 0, ..., g_N = 0
• `[Multi Gas stations & Line Case] (accounts for 18% of cases) -> Roads are on a straight line. M = N -1, u_j = j, v_j = j + 1 (1