DSA Homework 5

Data Centers

Little John is all grown up now and working in a high tech data center. One day, as he got to work, he finds out that hackers attacked his network and managed to disable some of the servers. A disabled server can't route data in or out, so they behave as all links to and from those nodes are disabled. Some of the remaining servers are critical to data access within his company and he wants to know if there is still a route for the data between them.

Help Little John write a program to find out if those servers are still linked.

Requirement

Given a number of servers N and an adjacency matrix NxN specifying the links between those servers, a number K of failed servers, and pair of servers (i, j), specify if there is still a route between server i and server j.

Input Data

A file called data_center.in, containing the number of servers N on the first line and N x N subsequent values, defining the adjacency matrix, arranged in a square, on N lines, followed by the number K of failed servers, K values specifying the servers on the following line, and the pair (i, j) on the last line.

Output Data

A file called data_center.out, containing the value 0 if there is no route between the two specified servers and 1 if there is.

Restrictions

1 ≤ K ≤ N ≤ 1000

Examples

5
0 1 1 0 0
1 0 1 0 0
1 1 0 1 1
0 0 1 0 1
0 0 1 1 0
1
3
0 4

Input	Output	Comments
5 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 0 1 1 0 1 2 0 4	0	The data center has 5 nodes. There is only 1 failed node: node 2. The critical servers are 0 and 4 and since there is no route between them, the result is 0.
1	The data center has 5 nodes. There is only 1 failed node: node 3. The critical servers are 0 and 4 and since there is now a route between them, the result is 1.