Bridge Blasting Harvest

This is an Agentics migration of Frontier-CS algorithmic problem 306.

Your submitted zip_project run command is executed once per case. It receives exactly one case on stdin and must write the candidate answer to stdout. Do not read or write challenge-owned files. Network access is unavailable during setup, build, and run.

The trusted separated evaluator uses the original Frontier-CS Testlib checker. Public validation is intentionally small and only checks the interface. Official scoring uses the private Frontier-CS-derived run manifest.

Original Statement

Scorched Bridges Campaign

Problem

The enemy controls an archipelago of islands connected by bridges. Their headquarters is on island 1.

You have obtained a forecast of the next m days. On day i, several islands will contain energy depots. If an island with a depot is still connected to island 1, the enemy harvests its energy that day. If it is disconnected from island 1, that depot is denied.

You may prepare a long-term demolition campaign:

• A bridge can be rigged in advance, paying a one-time installation cost.
• On any day, you may detonate any subset of rigged bridges, paying a per-use cost for each detonation.
• Destroyed bridges are repaired by the enemy overnight, so each day starts from the original graph again.
• Each rigged bridge has a limited number of times it can be detonated during the whole campaign.
• Your demolition teams also have a daily limit on how many bridges they can blow up on each day.

Your task is to output any feasible campaign plan. The judge will compute its total cost, combining your demolition expenses and the total energy still harvested by the enemy. Lower is better.

Because the graph is general and decisions interact across many days, exact optimization is intended to be intractable; heuristic approaches are expected.

Input

The first line contains two integers:

• n — number of islands
• e — number of bridges

Islands are numbered from 1 to n.
Bridges are numbered from 1 to e in input order.

The next e lines each contain five integers:

• u_j, v_j — endpoints of bridge j
• a_j — installation cost to rig bridge j
• b_j — cost each time bridge j is detonated
• c_j — maximum number of days bridge j may be detonated over the whole campaign

Then follows one integer:

• m — number of forecast days

The next m lines describe the days.
Line i contains:

• r_i — number of energy depots on day i
• L_i — maximum number of bridges you may detonate on day i
• then 2 * r_i integers:
  • h_1, v_1, h_2, v_2, ..., h_{r_i}, v_{r_i}

meaning island h_t has a depot worth v_t energy on day i.

Guarantees

• The bridge graph is connected.
• h_t != 1 for all depots.
• Within one day, all depot islands are distinct.

Output

Your output must describe one campaign plan.

• First line: one integer x — number of rigged bridges.
• Second line: x distinct integers — the IDs of the rigged bridges, in any order.
  If x = 0, this line should be empty.

Then output m lines.
On day i, output:

• d_i — number of bridges detonated on day i
• followed by d_i distinct bridge IDs

Feasibility requirements

Your output is feasible iff all of the following hold:

1. Every listed bridge ID is between 1 and e.
2. The rigged bridge list contains no duplicates.
3. On each day, the detonated bridge list contains no duplicates.
4. Every detonated bridge must be rigged.
5. For each day i, d_i <= L_i.
6. For each bridge j, it is detonated on at most c_j different days over the entire campaign.

If your output is infeasible, the score for that test is 0.

Objective

For each day i:

1. Start from the original graph.
2. Remove all bridges detonated on day i.
3. Any depot island still connected to island 1 contributes its value to the enemy's harvested energy that day.
4. Any depot island disconnected from island 1 contributes 0.

Let:

• InstallCost = sum of a_j over all rigged bridges
• BlastCost = sum of b_j over all detonations on all days
• Harvested = sum of values of all depots that remain connected to island 1 on their respective days

Your objective value is

F = InstallCost + BlastCost + Harvested

You must minimize F.

Scoring

For each test file, define the baseline solution as:

• rig no bridges,
• detonate no bridges on every day.

Its objective value is

B = sum of all depot values on all days.

For a feasible submission with objective value F, the test score is

Score_test = min(1000, 100 * B / max(1, F))

An infeasible submission receives Score_test = 0.

The final score is the arithmetic mean of Score_test over all test files.

Notes:

• The baseline always scores exactly 100 on every test.
• Better solutions score higher than 100.
• A solution at least 10 times better than the baseline is capped at 1000 on that test.

Constraints

• 2 <= n <= 2 * 10^5
• n - 1 <= e <= 3 * 10^5
• 1 <= m <= 2 * 10^5
• 1 <= u_j, v_j <= n, u_j != v_j
• 1 <= a_j, b_j <= 10^6
• 1 <= c_j <= 20
• 1 <= r_i < n
• 0 <= L_i <= 20
• 1 <= v_t <= 10^6
• sum r_i <= 5 * 10^5
• sum L_i <= 5 * 10^5

Constraints

• Time limit: 8 seconds
• Memory limit: 512 MB

Example

Input

5 4
1 2 5 2 2
2 3 2 1 1
2 4 2 1 1
1 5 4 2 1
2
2 1 3 10 4 8
2 2 5 12 3 5

Output

2
1 4
1 1
2 1 4

Explanation

• Rig bridges 1 and 4.
• Day 1: detonate bridge 1 (1-2), disconnecting islands 3 and 4.
• Day 2: detonate bridges 1 and 4, disconnecting islands 3 and 5.

Costs:

• Installation: 5 + 4 = 9
• Detonation: day 1 uses bridge 1 (2), day 2 uses bridges 1 and 4 (2 + 2), total 6
• Harvested energy: 0

So F = 9 + 6 + 0 = 15.

Baseline value:

• Day 1: 10 + 8 = 18
• Day 2: 12 + 5 = 17
• B = 35

Therefore this output gets

Score_test = 100 * 35 / 15 = 233.333...