# 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
```text
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
```text
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...`
