Shortest Path Recovery

Limits 1s, 512 MB · Interactive

Mr. Biscuit is in trouble. He accidentally deleted all the programs in his server and his database is corrupted as a result. There was a graph contained in the database. The graph had a source node and  the shortest paths from the source node to the other nodes was calculated using a function called SSSP. Mr. Biscuit has found the pseudocode of the function in his notebook. The pseudocode is given below:

Input: A weighted graph G with vertices V and edges E
procedure SSSP(G,source):
1  Let N ← number of nodes in G
2  Let D[] ← 100000000 // D is an one dimensional array of size N
3  D[source] = 0
4  for step from 1 to N
5      for all edges from (u,v) in E
6          if D[u] + cost[u][v] < D[v]
7              D[v] = D[u] + cost[u][v]
8          end if
9      end for
10 end for
11 return D

While running the function to achieve the result, the array DD was stored in the database after each iteration of the loop starting at line 44. So, if the loop iterates XX times, the database will save XX copies of DD, possibly with different values. Thus, after each iteration, the array DD may be updated with the information about the shortest path of each node from the source.

Now, the database has been corrupted and Mr. Biscuit has lost the results regarding the shortest paths of the nodes. He also lost the original graph, but remembers that none of the weights of the edges of that graph had an absolute value over 10001000. After a few days of relentless effort, he managed to salvage the values of all the indices of DD after each iteration of the loop. Mr. Biscuit has saved all these data in a temporary backup server. It could be the case that the shortest paths may be retrievable from the data that has been salvaged.

You will have to find if there exists shortest paths from the source node to all the other nodes in the original graph. For retrieving the result, you can perform some queries from the data that Mr. Biscuit has salvaged. Since the backup server has limited resources, you can only perform a limited number of such queries to make your decision correctly.

Interaction

You can make three types of interactions in this problem:

  1. 11: The contestant will start the interaction by printing a 11, the contestant will receive the value of NN as a response after this interaction. This type of interaction will occur only once at the start of the communication.

  2. 22 tt ii jj The contestant will ask for a sub-array from index ii to jj (i<=j,0<=i,j,<Ni<=j, 0 <= i, j, < N) after the t’th (1<=t<=N1 <= t <= N) iteration of the loop at line 44 of the pseudocode. In response, the contestant will get the values from index ii to index jj of the array DD after the t’th iteration of the function SSSP. A contestant can make at most 2N2 * N interactions of this type. Each interaction should be valid.

  3. 3 result: After all the interactions of type 11 and type 22, a contestant will print the result in the last line of interaction. The result should be 11, if there are shortest paths from the source to all the other nodes of the graph. Otherwise, the result should be 00.

Constraints

Subtask #1 (10 points)

N=1N = 1

Subtask #2 (10 points)

N=2N = 2

Subtask #3 (25 points)

N=3 N = 3

Subtask #4 (55 points)

N<=500 N <= 500

Sample Interaction

After at most 2N2 * N queries of type 22, you will have to answer 11 if there exists shortest paths from the source node to all the other nodes in the original graph or 00 otherwise. The result should be printed in the format mentioned in the interaction section. If you give an invalid query of any type, or if you request for an invalid query, you will receive a verdict of Wrong Answer.

For example, if N=3N = 3, a sample interaction can be as follows:

input: 1

response: 3

input: 2 2 1 2

response: 7 12

input: 2 3 0 2

response: 0 7 12

input: 3 1

Input

“Since this is an interactive problem, please don’t forget to flush your output after printing each line. You may use fflush(stdout) for printf/cout in C/C++, import sys and sys.stdout.flush() in Python to flush the output. If you use some other programming language, consult its documentation.

To learn more about Interactive Problems: https://help.toph.co/toph/interactive-problems” - reborn

In the pseudocode, the cost[u][v] indicates the weight of the directed edge connecting the nodes u and v.