전등 스위치

Ann Britt-Caroline은 복권에 당첨되었다. 새로 얻은 재산으로 그녀는 개인용 제트기 한 대와 약간의 개인용 제트(제트: 작고 벨벳처럼 검은 석탄), 그리고 방 $N$개가 긴 복도로 연결된 거대한 집을 샀다. 각 복도는 두 방을 연결하지만, 반드시 어떤 특정한 기하학적 형태를 따르는 것은 아니며 아무 두 방이나 연결할 수 있다. Ann은 열성적인 환경운동가이므로 불필요하게 전등을 켜 두는 일이 절대 없도록 노력한다. 그녀는 현재 방 $1$에 서 있으며(전등이 켜진 유일한 방이다), 방 $N$이 더 흥미로운 장소일지도 모른다고 생각한다.

안타깝게도 Ann Britt-Caroline은 어둠을 무서워한다. 그녀는 전등으로 밝혀지지 않은 복도를 절대 지나가고 싶어 하지 않는다. 다행히 방에서 인접한 복도로 빛이 일부 새어 나갈 수 있다. 각 방에 대해 Ann은 그 방의 전등이 켜졌을 때 인접한 복도 중 어느 복도가 밝혀지는지 알고 있다. 어떤 방의 전등은 인접한 복도 중 일부를 밝힐 만큼 강하지 않을 수 있지만(또는 복도가 빛과 잘못된 각도를 이룰 수 있지만), 그 복도 반대편 방의 전등은 밝힐 수 있다. 이 경우에는 반대편 전등이 켜져 있을 때에만 그 복도를 지나갈 수 있다.

Ann Britt-Caroline은 이제 집 안을 돌아다니며 전등을 켜고 끈 뒤, 다른 어떤 방의 전등도 켜져 있지 않은 상태로 방 $N$에 도착할 수 있는지 궁금해한다. 가능하다면, 그 과정에서 켜야 하는 전등의 최소 개수도 궁금해한다.

채점

여러 테스트 케이스 그룹으로 해답을 테스트한다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ | $13$ | $N \le 15, M \le 60$

$2$ | $33$ | $N \le 50, M \le 200$

$3$ | $34$ | 방들은 일직선 위에 있다. 각 $i$에 대해 방 $i$의 전등은 방 $L, \dots, R$에 있는 복도들을 밝히며, 어떤 $L \le i \le R$가 존재한다

$4$ | $20$ | 추가 제한 없음

입력의 첫째 줄에는 방의 개수를 나타내는 정수 $N$ ($1 \le N \le 500$)이 주어진다.

다음 $N$개의 줄에는 방에 대한 설명이 주어진다. $i$번째 줄에는 먼저 수 $s_i$ ($0 \le s_i < N$)이 주어지고, 이어서 방 $i$의 전등이 밝히는 복도를 통해 Ann이 갈 수 있는 방들을 나타내는 $s_i$개의 정수 $a_1, \dots, a_s$ ($1 \le a_j \le N, a_j \neq i$)이 주어진다.

모든 $s_i$의 합을 $M$라고 하자. 그러면 $0 \le M \le 2000$이다.

다른 모든 방의 전등이 꺼진 상태로 방 $N$에 도착할 수 없다면 ```nej`''을 출력한다. 그렇지 않으면 그곳에 도착하기 위해 Ann Britt-Caroline이 켜야 하는 서로 다른 전등의 최소 개수를 나타내는 정수 하나를 출력한다.

첫 번째 예제에서 Ann이 사용할 수 있는 한 가지 전략은 먼저 방 3으로 가서 그 방의 전등을 켜는 것이다. 그다음 방 1로 가서 그 방의 전등을 끈 뒤, 방 3의 전등이 밝히는 복도를 통해 방 3으로 돌아갈 수 있다. 그다음 방 4로 가서 그 방의 전등을 켜고, 방 5(목적지)로 가서 그 방의 전등도 켤 수 있다. 그런 다음 방 4로 돌아가 그 방의 전등을 끄고, 방 3으로 가서 그 방의 전등을 끈 뒤, 마지막으로 방 3에서 방 5로 갈 수 있다. 총 세 개의 전등(방 3, 4, 5의 전등)을 켰다.

두 번째 예제에서는 원하는 상태에 절대 도달할 수 없다. 방 1의 전등을 끈 뒤 그 방을 떠나는 것이 절대 불가능하기 때문이다.