| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 40 | 17 | 9 | 42.857% |
3025년, 정예우주공군으로서 기본군사훈련단에 입소한 하늘이는 지구 저궤도에 트리 모양으로 신설된 신병트리대대에 배정되어 불침번 근무를 서게 되었다.
신병트리대대는 그 이름에 걸맞게 $N$개의 방이 있으며, $N-1$개의 복도가 서로 다른 방들을 사이클이 없는 트리 구조로 연결하고 있다. 구체적으로 $i$번 방은 $k_i$개의 방과 복도로 직접 연결되어 있으며, 이들의 방 번호는 $v_{i,0}, v_{i,1}, \cdots, v_{k_i - 1}$이다.
하늘이는 신병트리대대의 복잡한 트리 구조 속에서 길을 잃지 않고 순찰할 수 있도록 다음과 같은 특별한 순찰 규칙을 세웠다.
하늘이가 모든 방의 번호를 최소 한 번씩은 순찰 일지에 기록할 때까지 위 과정을 반복할 때, 하늘이가 복도를 통해 다른 방으로 이동해야 하는 총 횟수와 마지막으로 도착하는 방의 번호를 구하여라. 만약 하늘이가 모든 방을 방문할 수 없다면 $-1$을 출력한다.
첫째 줄에 방의 개수 $N$(2ドル \le N \le 2 \times 10^5$)이 주어진다.
다음 $N$개의 줄에 신병트리대대의 구조가 주어진다. 이 중 $i$번째 줄에는 $k_i+1$개의 정수 $k_i, v_{i, 0}, v_{i, 1}, \cdots, v_{i, k_i - 1}$가 공백을 사이에 두고 주어진다.
모든 방을 방문할 수 있다면, 첫째 줄에 총 이동 횟수와 마지막으로 도착한 방 번호를 공백을 사이에 두고 출력한다.
만약 모든 방을 방문하는 것이 불가능하다면 첫째 줄에 $-1$을 출력한다.
6 1 2 4 5 1 3 4 1 2 2 2 6 1 2 1 4
17 6
하늘이는 1ドル \rightarrow 2 \rightarrow 5 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 4 \rightarrow 2 \rightarrow 5 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 4 \rightarrow 6$ 순으로 순찰을 진행하게 된다.