Contest Test Data Generator for Graph Problems

In this problem, you are tasked with generating test data for two graph problems in a programming contest. The contest features two tasks: the Single Source Shortest Path (SSSP) problem and the Mystery problem. For SSSP, you are given a directed weighted graph along with Q queries. For each query, you need to compute the shortest path from a source s to a target t; if no path exists, output (10^9). For the Mystery problem, you are given an undirected graph. Your task is to assign each vertex a number from (0) to (X-1) such that any two directly connected vertices have different numbers, and you must output the minimum possible value of (X).

The input begins with a type indicator. If the first integer is 1, then the SSSP problem is to be solved. Otherwise, if the first integer is 2, the Mystery problem is to be solved.

For SSSP (type 1), the input format is:

(n) (m)\n u (v) w (repeat m times)\n (Q)\n s t (repeat Q times)

For the Mystery problem (type 2), the input format is:

(V) (E)\n u v (repeat E times)

Your program should output Q lines for SSSP (each containing the shortest path distance or (10^9) if unreachable) or a single integer for the Mystery problem (the minimal (X)).

inputFormat

The first integer in the input is a type indicator:

• If it is 1, the problem is SSSP. The following input is provided: • A line with two integers (n) and (m) (the number of nodes and edges). • Then (m) lines follow; each contains three integers: u, v, w, representing a directed edge from u to v with weight w. • Next, an integer (Q) denoting the number of queries. • Then (Q) lines follow, each with two integers s and t, representing a query from node s to node t.

• If it is 2, the problem is Mystery. The following input is provided: • A line with two integers (V) and (E) (the number of vertices and edges). • Then (E) lines follow; each contains two integers u and v, representing an undirected edge between u and v.

outputFormat

For the SSSP problem (type 1), output exactly (Q) lines. The ith line should contain the shortest path distance from s to t for the ith query, or (10^9) if no such path exists.

For the Mystery problem (type 2), output a single integer: the smallest integer (X) such that it is possible to assign each vertex a number in the range ([0, X-1]) with every pair of adjacent vertices receiving different numbers.

sample

1
5 6
0 1 2
1 2 3
0 3 1
3 2 1
2 4 5
1 4 10
3
0 2
0 4
3 4

2
7
6