Problem Description

Country R has $n$ cities, numbered from $1$ to $n$. Between every pair of cities there are roads, forming a graph. However, these roads are poorly built: each road has a fixed direction, and cars can only travel in that direction. Also, each road is one-time use, meaning at most one car can pass through it.

Now Country R is making a disaster prevention and mitigation plan. You need to help Country R compute, if city $t_i$ suffers a disaster, and the cities $s_{i,1}, s_{i,2}, \dots, s_{i,k_i}$ have enough relief supplies (you may assume each of them has supplies that can load infinitely many cars), then at most how many cars of supplies can be transported from these cities to $t_i$. Cars can only use the one-time roads between cities, but before reaching $t_i$, a car may pass through multiple cities and multiple roads for transfer.

Input Format

There are $n + m + 1$ lines in total.

The first line contains two positive integers $n, m$, denoting the number of cities and the number of queries.

Lines $2$ to $n + 1$ each contain a $01$ string of length $n$. In line $i + 1$, column $j$ indicates whether there is a road from $i$ to $j$ ($1$ means yes, $0$ means no).

In the next $m$ lines, each line starts with a positive integer $t_i$, then a positive integer $k_i$, followed by $k_i$ positive integers $s_{i,1}, s_{i,2}, \dots, s_{i,k_i}$. It is guaranteed that $s_{i,1}, s_{i,2}, \dots, s_{i,k_i}$ contain no duplicates and none of them equals $t_i$.

Output Format

Output $m$ lines, each containing a non-negative integer, representing the answer to the $i$-th query.

5 2
01001
00110
10001
10101
01000
2 2 1 4
5 2 4 1

2
3

见选手目录下的 road/road2.in 与 road/road2.ans。

见选手目录下的 road/road2.in 与 road/road2.ans。

Hint

Sample 1 Explanation

The roads between cities are shown in the figure below:

This is one possible plan corresponding to the answers:

In the first query, one car takes $1 \rightarrow 2$, and another takes $4 \rightarrow 1 \rightarrow 5 \rightarrow 2$.

In the second query, one car takes $1 \rightarrow 5$, one takes $1 \rightarrow 2 \rightarrow 3 \rightarrow 5$, and another takes $4 \rightarrow 5$.

Subtasks

For all testdata, it is guaranteed that $1 \le n \le 3000$, $1 \le m, \sum\limits_{i=1}^m k_i \le 30000$.

Special Property A: it is guaranteed that all queries have the same $t_i$.

Special Property B: it is guaranteed that the road between $u$ and $v$ goes from $\min(u, v)$ to $\max(u, v)$.

Translated by ChatGPT 5