Disaster Relief Logistics

R country has \( n \) cities labeled from 1 to \( n \). Every pair of cities is connected by a one‐way road, forming a tournament graph. However, these roads are in poor condition and each road can be used at most once (i.e. only one vehicle can pass through a given road). In the event of a disaster in a target city \( t \), some cities (the supply cities) have abundant relief materials. A vehicle may start from any of these supply cities and follow a path (possibly passing through several cities) to deliver supplies to \( t \), but no road may be used more than once overall.

Your task is to determine, for each query, the maximum number of vehicles that can be simultaneously routed along edge‐disjoint paths from the supply cities to the disaster city \( t \). The road network is given in an \( n \times n \) matrix. The \( j^{th} \) number in the \( i^{th} \) row is 1 if there is a road from city \( i \) to city \( j \) (and 0 otherwise). It is guaranteed that for any two distinct cities \( i \) and \( j \), exactly one of \( (i, j) \) and \( (j, i) \) is 1, and all diagonal entries are 0.

The input includes multiple queries. Each query is specified by a target city \( t \) and a list of supply cities. For each query, compute the maximum number of relief vehicles that can reach city \( t \) via edge-disjoint paths.

inputFormat

The first line contains an integer \( n \) representing the number of cities.

The next \( n \) lines each contain \( n \) integers (each 0 or 1) separated by spaces, representing the road matrix. The \( j^{th} \) integer in the \( i^{th} \) line is 1 if there is a road from city \( i \) to city \( j \), and 0 otherwise. For any \( i \neq j \), exactly one of \( (i, j) \) and \( (j, i) \) is 1. The diagonal entries are all 0.

The following line contains an integer \( q \) representing the number of queries.

Each of the next \( q \) lines describes a query. Each query begins with two integers: \( t \) (the target city) and \( k \) (the number of supply cities), followed by \( k \) distinct integers indicating the supply cities.

outputFormat

For each query, output a single integer on a separate line — the maximum number of vehicles that can be sent from the supply cities to city \( t \) using edge-disjoint paths.

sample

3
0 1 0
0 0 1
1 0 0
2
3 2 1 2
2 2 1 3

1
1