Medieval Roads X52557

In March 1495 a coalition of different provinces and armies called the “League of Venice” was formed in Italy, ready for the battle to repel the French invasion. During the battle the roads were occupied by armies with some regularity.

Michelangelo wants to travel from Rome to Venice as fast as possible, but he cannot choose the roads that are occupied by armies. Help him compute the minimum number of days required to travel from Rome to Venice, given a set of roads R that interconnect cities.

Each day Michelangelo can travel on a road or choose to remain in the current city. He is only allowed to visit each city once, although this visit can last for multiple days. The i-th road is open if i is even and the day is even, or i is odd and the day is odd, else roads are closed because of the armies using them.

Input

The input consists of several test cases. Each test case consists of a number N of cities such that 2≤ N≤ 1000, followed by N lines with the name of each city. The next line contains a number R of roads such that 1 ≤ R ≤ N(N−1)/2, followed by R lines containing bidirectional roads described by the name of two cities that the road connects. The first road is even (0), the second is odd (1), etc., and Michelangelo starts travelling on day 0.

Output

For each test case, print the minimum number of days required for Michelangelo to travel from Rome to Venice.

In this example, Michelangelo starts in Rome and the shortest route to Venice is through Florence, so 2 days would be required, but the armies occupy the road between Florence and Venice when Michelangelo arrives at Florence, so he has to wait one day and the total travel time is 3 days.