2562번 - 게임 오브 데쓰 (Hard)

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

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

형진이는 자신을 포함해 $N$명이서 술게임을 하게 됐다!
게임이 시작되면 모든 참가자들은 $1$번부터 $N$번까지의 번호를 부여 받고 왼손과 오른손으로 자신을 제외한 다른 사람을 지목해야 한다. 같은 사람을 두 번 지목할 수도 있다.
이제 $1$번 참가자가 $10 \leq K \leq 99$ 범위의 양의 정수 $K$를 정해 말한 후 지목한 사람 중 한 명 에게 $K$의 값을 $1$ 줄여 넘긴다.
$K$를 받은 사람은 다시 지목한 사람중 한 명 에게 $K$의 값을 $1$ 줄여 넘기고 이 과정을 계속 반복해 $K$가 $0$이 된 사람이 술을 마시게 된다.

이번에 형진이가 $1$번을 부여받아 $K$를 정하게 되었다. 모든 사람이 누구를 지목한지 형진이의 눈에 보일때 이번에 절대로 자신이 걸리지 않도록 하는 $K$를 정해보자. 단, 첫 턴을 포함해 자기 자신에게 턴이 왔을 경우 형진이는 어느 쪽으로 지목할지를 선택할 수 있다. 만약 어떠한 $K$를 고르더라도 자신이 걸릴 수 있다면 $-1$을 출력한다.

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

다음 $N$개의 줄에 걸쳐 $i$번 사람이 지목한 두 명의 사람 정보 $L_i$, $R_i$가 공백을 사이에 두고 주어진다. ($1 \le L_i, R_i \le N$) 이는 $i$번 사람이 $L_i$, $R_i$번 사람을 지목했다는 뜻이다.

자신이 절대로 걸리지 않도록 하는 어떠한 숫자 $K$를 출력한다. 만약 그러한 숫자가 존재하지 않다면 $-1$을 출력한다.