Making test data 1

Writing a good contest problem is hard. The hardest part is often the test data. Good tests must separate a solution that follows the intended approach from one that does not. They must also catch a program that is right on most inputs and fails only on a special case.

This task does not ask you to compute shortest paths. It asks you to print test data.

Build one input $X$ for a weighted directed shortest-path problem. $X$ must satisfy both of the following for the two programs below.

1. Modified Dijkstra must not time out on $X$.
2. Floyd-Warshall must time out on $X$.

Smaller data is better. $X$ may contain at most $10^7$ integers.

Both programs keep a $\mathrm{counter}$ of operations. If $\mathrm{counter}$ exceeds $10^6$, the program times out.

$X$ uses this format.

The first line is the number of vertices $V$. Vertices are numbered from $0$ to $V-1$.

Each of the next $V$ lines describes the outgoing edges of one vertex, starting from vertex $0$. The first number on the line is the out-degree $n_i$, followed by $n_i$ pairs $(j, w)$. Each pair is an edge from that vertex to $j$ with weight $w$.

The next line is the number of queries $Q$. Each of the next $Q$ lines has a start $s$ and a target $t$.

The data must obey these limits.

• $1 \le V \le 300$
• $n_i$ is a non-negative integer
• $0 \le j < V$
• $|w| < 10^6$
• $0 \le \sum n_i \le 5000$
• $1 \le Q \le 10$
• $0 \le s, t < V$
• no query start can reach a negative cycle

If a pair is unreachable, its shortest-path value is $10^9$.

If several inputs satisfy the conditions, keep the one with the fewest integers. If there is still a tie, compare the integers in the order they appear as a sequence and keep the lexicographically smallest sequence.

There is no input.

Print the unique input chosen by the rules above.

The first line is $V$.

Each of the next $V$ lines is the out-degree and the edge list of one vertex. If a vertex has no outgoing edges, print $0$ on that line.

The next line is $Q$.

Each of the next $Q$ lines is $s$ and $t$ separated by a space.

Floyd-Warshall runs on an adjacency matrix $M$ as follows.

counter = 0
for k = 0 to V-1:
    for i = 0 to V-1:
        for j = 0 to V-1:
            counter = counter + 1
            if counter > 1000000: TLE
            M[i][j] = min(M[i][j], M[i][k] + M[k][j])

The iteration count is always $V^3$. It does not depend on the number of edges or queries.

Modified Dijkstra runs the following for each query $(s, t)$. Initially $\mathrm{dist}[s] = 0$ and every other distance is infinite.

counter = 0
for each query (s, t):
    dist[s] = 0
    pq.push((0, s))
    while pq is not empty:
        counter = counter + 1
        if counter > 1000000: TLE
        (d, u) = pop(pq)
        if d == dist[u]:
            for each edge (u, v, w):
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    pq.push((dist[v], v))

$\mathrm{counter}$ is the number of priority-queue pops. If a vertex is relaxed more than once, it can enter the queue more than once.