JOIN

 Problem Statement

Problem Statement for LongLongTripDiv1

### Problem Statement

There is a country with N cities. The cities are numbered 0 through N-1. There are some bidirectional roads in the country. Each road connects a pair of cities. More precisely, for each i, road i connects the cities A[i] and B[i].

Limit is a deer that likes to travel along the roads. Traveling along road i (in either direction) takes him exactly D[i] minutes. Limit does not like cities, so he never waits in a city.

Limit is currently in the city 0, starting his travels. In exactly T minutes, he wants to be in the city N-1.

You are given the int N; the int[]s A, B, and D; and the long T. Return "Possible" (quotes for clarity) if Deer Limit can reach city N-1 in exactly T minutes. Otherwise, return "Impossible".

### Definition

 Class: LongLongTripDiv1 Method: isAble Parameters: int, int[], int[], int[], long Returns: String Method signature: String isAble(int N, int[] A, int[] B, int[] D, long T) (be sure your method is public)

### Constraints

-N will be between 2 and 50, inclusive.
-A will contain between 1 and 50 elements, inclusive.
-A, B and D will each contain the same number of elements.
-Each element in A and B will be between 0 and N-1, inclusive.
-Each element in D will be between 1 and 10,000, inclusive.
-For each valid i, A[i] and B[i] will be different.
-No two roads will connect the same pair of cities.
-T will be between 1 and 10^18, inclusive.

### Examples

0)

 `3` `{0,0,1}` `{2,1,2}` `{7,6,5}` `11`
`Returns: "Possible"`
 city 0 -> city 1 -> city 2 is a valid way.
1)

 `3` `{0,0,1}` `{2,1,2}` `{7,6,5}` `25`
`Returns: "Possible"`
 city 0 -> city 2 -> city 1 -> city 0 -> city 2 is a valid way.
2)

 `2` `{0}` `{1}` `{1}` `9`
`Returns: "Possible"`
 Here, Limit just travels back and forth between cities 0 and 1 along the only road in the country.
3)

 `2` `{1}` `{0}` `{1}` `1000000000000000000`
`Returns: "Impossible"`
4)

 `4` `{0,0,1}` `{2,1,2}` `{10,10,10}` `1000`
`Returns: "Impossible"`
 In this test case, there is absolutely no way how to reach city N-1 from city 0.
5)

 `9` `{4,8,5,8,3,6,2,6,7,6,6}` `{2,7,1,5,1,3,1,1,5,4,2}` `{6580,8822,1968,673,1394,9337,5486,1746,5229,4092,195}` `937186357646035002`
`Returns: "Impossible"`

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
Single Round Match 615 Round 1 - Division I, Level Two