问题 1825 --Logical Chain1825: Logical Chain
时间限制: 10 Sec 内存限制: 128 MB
提交: 1 解决: 1
[提交][状态][讨论版][命题人:]题目描述
Every time you come across a problem you've never seen before, haven't you thought of something that is familiar to you? If so, you might think of something else, then more and more things will come to your mind. This is what is called ''Logical Chain''. Lu Xun's work also described such interesting phenomenon.
Assume there are n
things, labeled by 1,2,...,n
. Little Q's mind can be expressed by a n×n
matrix g
. If he can think of j
when he comes across i
, then gi,j
is 1
, otherwise it's 0
. For two different things u
and v
, if u
can lead to v
directly or indirectly and v
can also lead to u
directly or indirectly, then the pair (u,v)
is called a ''Looping Pair''.
Little Q's mind changes all the time. On i
-th day, there are ki
positions (u,v)
in matrix g
flipped(0
to 1
and 1
to 0
). Please write a program to figure out the number of ''Looping Pairs'' after each day's all changes.
Note : (u,v)
and (v,u)
should not be counted twice. 输入描述
The first line of the input contains an integer T(1≤T≤15), denoting the number of test cases.
In each test case, there are 2 integers n,m(1≤n≤250,1≤m≤25000) in the first line, denoting the number of things and days.\par
For the next n lines, each line contains n integers gi,1,gi,2,...,gi,n(0≤gi,j≤1,gi,i=0), denoting the matrix g.
For the next m parts, there is an integer ki(1≤ki≤10) in the first line, denoting the number of changes happened on that day.
For the next ki lines, each line contains 2 integers u,v(1≤u,v≤n,u≠v), denoting a changed position in g.
It is guaranteed that each position will be changed at most once per day.
输出描述
For each day, print a single line containing an integer, denoting the number of ''Looping Pairs'' after that day's all changes.
样例输入
1
4 2
0010
1000
0000
0000
3
1 4
3 2
1 2
2
4 3
2 3
样例输出
3
6
来源
[提交][状态]
