뜨거운 감자 원리

'뜨거운 감자' 원리는 네트워크에서 패킷을 라우팅하는 방법이다. 주된 장점은 라우팅 테이블이 필요 없고, 라우팅 중에 패킷을 분석할 필요가 없다는 것이다.

네트워크는 $n$개의 노드로 이루어져 있고, 일부 노드 쌍은 네트워크 연결로 이어져 있다. 각 노드는 스케줄을 가진다. 노드 $i$의 스케줄은 노드 번호의 수열 $a_{i,0}, a_{i,1}, \ldots, a_{i, l_i - 1}$이다. 네트워크는 다음과 같이 틱 단위로 동작한다.

틱 $t$ 동안 네트워크에는 여러 패킷이 있을 수 있다. 각 패킷은 출발 노드와 목적지 노드를 가지며, 틱 동안 어떤 노드에 머문다. 각 패킷에는 등장 시각이 있으며, 이 틱의 시작에 출발 노드에서 생성된다. 틱 $t$ 동안 패킷이 목적지 노드에 있으면, 패킷은 시각 $t$에 배달된 것으로 보고 네트워크에서 사라진다. 그렇지 않으면 패킷은 노드 $a_{i, t \bmod l_i}$로 전달되고, 다음 틱의 시작에 그곳에 도착한다. 어떤 틱의 시작에 여러 패킷이 같은 노드에 도착하면, 그 패킷들은 모두 파괴된다.

이 라우팅 원리의 주된 단점은 장점에서 비롯된다. 라우팅 테이블과 패킷 분석이 없으므로, 모든 패킷이 배달되도록 노드의 스케줄과 패킷의 등장 시각을 아주 신중하게 골라야 한다. 잘 골라도 모든 패킷을 배달하지 못하는 경우가 많다.

네트워크 설명과 패킷 집합이 주어진다. 각 패킷에 대해 배달을 시도할지 정할 수 있다. 네트워크가 동작하는 동안 선택한 패킷이 모두 배달되도록, 배달을 시도할 패킷의 최대 개수를 구한다.

첫 줄에 노드 수 $n$이 주어진다 ($1 \le n \le 100$). 다음 $n$줄은 노드를 설명한다. $i$번째 노드는 먼저 스케줄 길이 $l_i$가 주어지고, 이어서 $l_i$개의 수 $a_{i,0}, a_{i,1}, \ldots, a_{i,l_i-1}$이 주어진다 ($1 \le l_i \le 8$, $a_{i,j} \ne i$).

다음 줄에는 패킷 수 $p$가 주어진다 ($1 \le p \le 100$). 이어서 $p$줄에 패킷이 하나씩 주어지며, 각 줄은 출발 노드 $s_i$, 목적지 노드 $d_i$, 등장 시각 $t_i$로 이루어진다 ($s_i \ne d_i$, $0 \le t_i \le 1000$).

첫 줄에 배달할 수 있는 패킷의 최대 개수 $k$를 출력한다. 둘째 줄에는 배달할 수 있는 패킷의 번호 $k$개를 출력한다. 패킷 번호는 입력에 주어진 순서대로 1부터 $p$까지이다.