Optimal Activity Scheduling

This problem involves scheduling a set of activities with dependency constraints. Each activity takes a given amount of time and may depend on other activities. Your task is to determine a valid order of execution such that all dependencies are satisfied. If a valid order exists, compute the total time required by summing the durations of all activities; otherwise, output -1.

The activities are numbered from 1 to \( n \), and the dependency information is provided in 1-indexed format. In other words, if activity \( i \) depends on activity \( j \), then activity \( j \) must be completed before activity \( i \) can begin.

Note: Activities are executed sequentially following the specified order. The total time is simply the sum of the execution times.

inputFormat

The input begins with a single integer \( n \) (\(1 \leq n \leq 10^5\)) which represents the number of activities.

Each of the following \( n \) lines describes one activity with the following format:

ti di a1 a2 ... adi

Where:

• ti is the time required to complete the \(i\)-th activity.
• di is the number of activities that the \(i\)-th activity depends on.
• If di > 0, it is followed by \( d_i \) integers representing the indices of the activities that must be completed before the \(i\)-th activity can begin.

outputFormat

If a valid scheduling order exists:

• The first line contains a single integer representing the total time required to complete all activities.
• The second line contains \( n \) space-separated integers denoting a valid order in which the activities can be completed.

If it is impossible to schedule all activities due to cyclic dependencies, output a single line containing -1.

## sample

4
1 0
2 1 1
3 2 1 2
2 1 3

8
1 2 3 4

</p>