게임 오브 데쓰 (Easy)

면접 대비

시간 제한1초메모리 제한1024 MB

요약

각 사람이 가리키는 두 사람으로 이루어진 방향 그래프에서, 1번에서 K번 이동한 끝이 1번이 되지 않는 K(10 이상 99 이하)를 찾습니다.

난이도: 보통10점 중 4점
유형: 그래프, BFS
정답자: 아직 제출이 없습니다

문제

이 문제는 "게임 오브 데쓰 (Hard)" 문제와 볼드체로 적혀 있는 부분의 조건이 다르다.

(아싸~) 신난다 (아싸~) 재미난다 더 게임 오브 데쓰! (빠밤)

인트로 구호의 마지막 '데쓰' 또는 '빠밤'과 동시에 참가자들은 아무나 손가락으로 가리킨다. 이후 주최자가 아무 수를 부르면, 주최자의 손가락에서 시작해 가리켜진 사람에게 넘어가며 수를 하나씩 센다. 이 과정이 계속 반복된다. (출처: 나무위키)

형진이는 본인을 포함해 $N$ 명과 술 게임을 하게 됐다. 게임이 시작되면 모든 참가자는 $1$ 번부터 $N$ 번까지 번호를 받고, 왼손과 오른손으로 자신을 제외한 다른 사람을 각각 한 명씩 지목해야 한다. 같은 사람을 두 번 지목할 수도 있다.

지목이 끝나면 $1$ 번 참가자가 $10 \leq K \leq 99$ 범위의 양의 정수 $K$ 를 정해 말한다. 그다음 $K$ 의 값을 $1$ 줄이고, 본인이 지목한 사람 중 한 명에게 차례를 넘긴다. 차례를 넘겨받은 사람도 $K$ 의 값을 $1$ 줄인 뒤 지목한 사람 중 한 명에게 차례를 넘긴다. 이 과정을 반복해서 $K$ 의 값이 $0$ 이 되는 순간 차례를 넘겨받은 사람이 패배하고 술을 마신다.

형진이를 포함한 $N$ 명은 모두 만취해 있다. 자신의 차례가 되면 지목한 두 명 중 무작위로 한 명에게 차례를 넘긴다. 같은 사람을 지목했다면 그 한 명에게 넘긴다. 형진이를 포함한 모든 사람은 본인이 어떤 상대에게 차례를 넘길지 알 수 없다.

이번에 형진이가 $1$ 번을 받아 $K$ 의 값을 정하게 되었다. 각 사람이 누구를 지목했는지 모두 주어졌을 때, 형진이가 패배하는 일이 없도록 적당한 $K$ 를 정해보자. 어떤 $K$ 를 고르더라도 형진이가 패배할 가능성이 있다면 -1을 출력한다.

입력

첫 번째 줄에 참여하는 사람 수 $N$ 이 주어진다. $(2 \le N \le 1\,000)$

다음 $N$ 개의 줄에는 각 참가자가 지목한 사람의 정보가 주어진다. $i$ 번째 줄에는 $i$ 번 참가자가 왼손과 오른손으로 지목한 사람의 번호 $L_i$ , $R_i$ 가 공백을 사이에 두고 주어진다. $(1 \le L_i, R_i \le N,$ $L_i \neq i,$ $R_i \neq i)$

출력

문제의 조건을 만족하는 $K$ ( $10 \le K \le 99$ )를 출력한다. 그러한 $K$ 가 존재하지 않으면 -1을 출력한다.

예제3

예제 1
입력
```
2
2 2
1 1
```
예상 출력
```
11
```
예제 2
입력
```
5
2 3
4 5
4 5
2 3
2 3
```
예상 출력
```
10
```
예제 3
입력
```
3
2 3
3 1
1 2
```
예상 출력
```
-1
```