Constructing a DAG from Cactus Graph Queries

Given an undirected connected cactus graph with n nodes and m edges, each edge having a length l (note that different edges may have different lengths), and q queries, your task is to construct a Directed Acyclic Graph (DAG) satisfying the following conditions:

• The DAG has at least n+q nodes and at most 1,200,000 nodes and 2,400,000 edges.
• For every edge directed from u to v, it holds that u > n and u \neq v.
• For the i^th query (where 1 \le i \le q), a point set is defined by two integers u and d. A node x (with 1 \le x \le n) belongs to this set if and only if the shortest path distance between u and x in the cactus is at most d (i.e. \(dist(u, x) \le d\)). For every such node x in the point set, there must be exactly one path from the node numbered n+i (a newly added node corresponding to the query) to x in the DAG.
• For every node x in \(\{1, 2, \dots, n\}\) that does not belong to the i^th point set, there must be no path from node n+i to x in the DAG.

Note: A cactus is defined as a connected graph in which any edge belongs to at most one simple cycle (a simple cycle is a cycle that does not repeat any vertex except the first and last).

Hint: A trivial solution is to construct a DAG with exactly n+q nodes by making the nodes \(n+1, n+2, \dots, n+q\) correspond to the q queries, and then, for each query \(i\), add a direct edge from node \(n+i\) to every cactus node that is in the corresponding point set. This ensures that there is exactly one path (a single direct edge) from node \(n+i\) to any node in the set, and no path to any node not in the set. Note that for every such edge, the source node \(n+i\) satisfies \(n+i > n\).

inputFormat

The input is given as follows:

1. The first line contains two integers n and m (n is the number of nodes in the cactus, and m is the number of undirected edges).
2. The next m lines each contain three integers u, v and l representing an edge between nodes u and v with length l.
3. The following line contains an integer q representing the number of queries.
4. The next q lines each contain two integers u and d describing a query. In the i^th query, the point set consists of all nodes x (with 1 ≤ x ≤ n) for which the shortest path distance from u is at most d in the cactus.

outputFormat

Output your constructed DAG in the following format:

1. The first line contains two integers M and K, where M is the total number of nodes in the DAG and K is the total number of edges.
2. Each of the following K lines contains two integers u and v representing a directed edge from node u to node v.

Remember that in your constructed DAG:

• The nodes are numbered from 1 to M with the original cactus nodes being 1 to n and the additional query nodes being n+1 to n+q.
• Every edge must be from a node numbered greater than n (i.e. one of the query nodes) to one of the original cactus nodes.
• For each query i (1 ≤ i ≤ q), there is exactly one path from node n+i to any cactus node that lies in the corresponding point set, and no path to any cactus node outside that set.

sample

3 3
1 2 1
2 3 1
3 1 2
1
2 1

4 3
4 1
4 2
4 3