등반

그림 제공: Graham Evans

Fiona는 숙련된 등반가이다. 그녀는 경험이 적은 등반가들이 지지대로 사용할 수 있도록 암벽의 전략적인 위치에 박아 넣을 못을 종종 몇 개 가져간다. Fiona는 암벽 어디든 오를 수 있지만, 못을 박으려면 균형을 잡아야 하므로 현재 박혀 있는 못들(또는 물론 바닥)을 딛고 서 있을 때만 못을 박을 수 있다. 그녀는 언제든 못을 빼서 나중에 다시 사용할 수 있다. 방문할 예정인 각 암벽에 대해, 그녀는 모든 전략 지점에 어떤 단계에서는 못이 박혀 있도록 못을 박고 빼는 세심한 계획을 세워 두었다.

어제 비가 왔으므로 암벽이 젖어 있을 것이고, 못을 빼는 것은 위험할 수 있다. 이 때문에 Fiona는 못 $p$를 박았을 때 딛고 설 수 있었던 것과 동일한 못들을 딛고 설 수 있는 경우에만 못 $p$를 뺄 것이다. 하지만 안타깝게도 Fiona의 기존 계획은 이 새로운 예방 조치를 고려하지 않으므로, Fiona는 계획을 갱신해야 하며 당신에게 도움을 요청했다. 그녀는 너무 많은 추가 못을 가지고 다니고 싶지 않으므로, 당신은 이전 계획에서 사용하던 것보다 최대 $10$배 더 많은 못을 사용하는 안전한 계획을 찾겠다고 약속했다. 그 약속을 지킬 수 있는가?

예를 들어, 첫 번째 예제 입력에 있는 전략 지점이 $5$개인 암벽을 생각해 보자. 지점 $1$은 지면에 가까우므로 어떤 지점에도 의존하지 않는다. 지점 $2$에 못을 박으려면 지점 $1$에 못이 박혀 있어야 하며, 지점 $3$도 마찬가지이다. 지점 $4$에 못을 박으려면 지점 $2$와 지점 $3$ 양쪽 모두에 못이 박혀 있어야 한다. 지점 $5$에 못을 박으려면 지점 $4$에 못이 박혀 있기만 하면 충분하다.

따라서 못을 박는지 빼는지에 따라 각각 $+$와 $-$로 표시한 수열 $+1,+2,+3,-1,+4,-2,-3,+5$은 건조한 환경에서 안전한 계획이며, 못 $3$개를 사용한다. 하지만 지점 $2$와 $3$의 못을 지지 없이 빼므로, 젖은 환경에서는 안전한 계획이 아니다. 수열 $+1,+2,-2,+3,-1,+4,-3,+5$에는 못이 $2$개만 필요하지만, 지점 $2$에 못이 없는 상태에서 지점 $4$에 못을 박으므로 전혀 안전하지 않다. 수열 $+1,+2,+3,-1,+4,+5$은 젖은 환경에서 안전한 계획이며, 못 $4$개를 사용한다.

첫 번째 줄에는 암벽의 전략 지점 수를 나타내는 정수 $n$이 주어진다 ($1 \leq n \leq 1\,000$). 이어지는 $n$개의 각 줄에는 정수 $p$ 하나 ($0 \leq p < n$)와 $p$개의 정수로 이루어진 목록이 주어진다. $i$번째 줄에 $x_1,\ldots,x_p$ ($1 \leq x_j < i$)가 주어지면, 지점 $i$에 못을 박기 위해 모든 지점 $x_j$에 못이 박혀 있어야 한다.

다음 줄에는 건조한 환경에서 안전한 계획의 단계 수를 나타내는 정수 $t$이 주어진다 ($1 \leq t \leq 1\,000$). 이어지는 $t$개의 각 줄에는 정수 $i$가 주어지며, 이는 지점 $i$에 못을 박거나 그 지점에서 못을 빼는 것을 의미한다.

건조한 환경에서 안전한 계획이 사용하는 못 개수의 최대 $10$배를 사용하는, 젖은 환경에서 안전한 계획이 없다면 $-1$을 출력한다. 그렇지 않으면 첫 번째 줄에 젖은 환경에서 안전한 계획의 단계 수를 나타내는 정수 $t$을 출력해야 한다 ($1 \leq t \leq 1\,000\,000$). 이어지는 $t$개의 각 줄에는 정수 $i$를 출력해야 하며, 이는 지점 $i$에 못을 박거나 그 지점에서 못을 빼는 것을 의미한다.