Climbing

Picture by Graham
Evans

Fiona is an expert climber. She often brings some pegs with her, which she nails in some strategic places in the rock wall, so that less experienced climbers can use them for support. Fiona can climb to anywhere in the wall, but hammering a peg needs some balance, so she can only place a peg if she is standing in currently placed pegs (or, of course, the floor). She can remove a peg at any time and reuse it later. For each wall she is planning to visit, she has a careful plan for how to place and remove pegs in such a way that every strategic point has a peg at some step.

Yesterday it was raining, so the rock will be wet and it can be unsafe to remove pegs. Because of this, Fiona will only remove a peg $p$ if she can stand on the same pegs as when $p$ was placed. Alas Fiona’s existing plans do not take this new precaution into account, so Fiona has to update her plans and she has asked you for help. She would like not to carry too many extra pegs, so you promised to find safe plans using at most $10$ times more pegs than her previous plans were using. Can you deliver on your promise?

For example, consider the wall in the first sample input with $5$ strategic points. Point $1$ is close to the ground so it does not depend on any point. There has to be a peg in point $1$ in order to put a peg in point $2$, and the same holds for point $3$. In order to put a peg in point $4$, there has to be a peg both in point $2$ and point $3$. To put a peg in point $5$ it is enough if there is a peg at point $4$.

Therefore, the sequence (with annotations $+$ and $-$ depending on whether we add or remove a peg) $+1,+2,+3,-1,+4,-2,-3,+5$ is a safe dry plan, and it uses $3$ pegs. However it is not a safe wet plan, because we remove the pegs at points $2$ and $3$ without support. The sequence $+1,+2,-2,+3,-1,+4,-3,+5$ only requires $2$ pegs, but it is not safe at all because we add a peg to point $4$ without there being a peg at point $2$. The sequence $+1,+2,+3,-1,+4,+5$ is a safe wet plan, and it uses $4$ pegs.

The first line contains an integer $n$ ($1 \leq n \leq 1\, 000$), the number of strategic points in a wall. Each of the following $n$ lines contains an integer $p$ ($0 \leq p < n$) and a list of $p$ integers. If line $i$ contains $x_1,\ldots ,x_ p$ ($1 \leq x_ j < i$), then all points $x_ j$ need to have a peg in order to place a peg in point $i$.

The next line contains an integer $t$ ($1 \leq t \leq 1\, 000$), the number of steps in the safe dry plan. Each of the following $t$ lines contains an integer $i$, meaning that a peg is being placed or removed from point $i$.

If there is no safe wet plan using at most $10$ times the number of pegs of the safe dry plan, output $-1$. Otherwise, the first line must contain an integer $t$ ($1 \leq t \leq 1\, 000\, 000$), the number of steps in the safe wet plan. Each of the next $t$ lines must contain an integer $i$, meaning that a peg is being placed or removed from point $i$.

Sample Input 1 | Sample Output 1 |
---|---|

5 0 1 1 1 1 2 2 3 1 4 8 1 2 3 1 4 2 3 5 |
6 1 2 3 1 4 5 |

Sample Input 2 | Sample Output 2 |
---|---|

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