Iron Islands

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
The Iron Islands is one of the constituent regions of the Seven Kingdoms, and it was formerly a sovereign nation under the same name, until the War of Conquest. The Iron Islands are home to a fierce people who call themselves the ironborn and are ruled by House Greyjoy from the castle of Pyke.
(c) A Wiki of Ice and Fire
The main problem of the Iron Islands is that there are a lot of them and it's not that easy to get from one island to another.
In this problem we assume, that the Iron Islands can be described as an unweighted directed graph G, which consists N vertices. G doesn't have selfloops and multiple arcs.
The Ironborns(the people of the Iron Islands) are trying to improve the arc infastructure. They have a big project, which is splited into Q phases. Each phase starts with changing M arcs(adding/deleting some of the arcs of G). After that, in order to collect some statistics, the phase continues with caculating the sum of the minimal distances for all reachable vertices from some vertex V.
Your task is pretty simple: write an algorithm to perform all the phases, correctly and quickly.
Note
Maybe, some of you aren't familiar with definitions from the statement. Here're some articles that could help you to understand the problem correctly:
 Directed graph: http://en.wikipedia.org/wiki/Directed_graph
Input
The first line of the input contains an integer T, denoting the number of testcases. The description of T testcases follows.
The first line of each testcase contains an integer N, denoting the number of vertices in G.
Each of the next N lines contains a string E_{i}, consisting of N symbols(only '0' and '1' are allowed). If j'th symbol of E_{i} equals to '1', then the arc from vertex i to vertex j belongs to G, otherwise there's no such arc.
The next line contains an integer Q, denoting the number of phases of the big project. The description of the phases follows.
The first line of a phase desription contains two integers V and M, denoting the vertex for caculating the sum of the minimal distances for all reachable vertices and the number of arcs to change.
The next M lines of a phase desription contains two integers A and B each, denoting the next arc A > B to change(it means, that if there's no A > B arc in G by that moment, then you should add it; if there's A > B arc in G, then you should delete it).
IMPORTANT: you should not roll back all the edges after each of the phases. It's ok for the graph to be changed during the big project.
Output
The output of each testcase should contain Q lines, i'th should contain one integer: the sum of the minimal distances for all reachable vertices from the corresponding vertex V.
Do not add any newlines between different testcases.
Constraints
 0 ≤ sum of M ≤ 250000, for each testcase.
 1 ≤ V, A, B ≤ N
 Subtask 1(20 points): 1 ≤ T ≤ 4, 1 ≤ N ≤ 100, 1 ≤ Q ≤ 100;
 Subtask 2(30 points): 1 ≤ T ≤ 3, 1 ≤ N ≤ 500, 1 ≤ Q ≤ 1000;
 Subtask 3(50 points): T = 1, 1 ≤ N ≤ 1000, 1 ≤ Q ≤ 10000.
Example
Input: 2 2 01 00 2 1 0 2 0 5 00101 00111 11011 11001 10100 5 1 3 1 4 2 5 5 3 2 1 1 2 3 1 2 1 4 1 1 2 5 3 2 4 4 2 2 4 Output: 1 0 5 6 4 5 8
Author:  kostya_by 
Tester:  stzgd 
Editorial  http://discuss.codechef.com/problems/IRONISL 
Tags  bfs, bitmasking, graph, kostya_by, ltime15, medium 
Date Added:  27072014 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions