32657번 - 게임 오브 데쓰 (Hard) 스페셜 저지

문제

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

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

지목이 끝나면 1ドル$번 참가자가 10ドル \leq K \leq 99$ 범위의 양의 정수 $K$를 정해 말한 후, $K$의 값을 1ドル$ 줄인 뒤 본인이 지목한 사람 중 한 명에게 차례를 넘긴다. 차례를 넘겨받은 사람은 다시 $K$의 값을 1ドル$ 줄인 뒤 지목한 사람 중 한 명에게 차례를 넘기고, 이 과정을 계속 반복해 $K$의 값이 0ドル$이 됨과 동시에 차례를 넘겨받은 사람이 패배하며 술을 마시게 된다.

형진이를 제외한 $N - 1$명은 모두 만취했기에, 자신의 차례가 되면 자신이 지목한 둘 (같은 사람을 지목한 경우 하나) 중 무작위로 한 명에게 차례를 넘겨준다. 즉, 형진이를 제외한 모든 사람은 본인이 어떠한 상대에게 차례를 넘겨줄지 알 수 없다. 하지만 주량을 잘 조절한 형진이는 만취하지 않았기에 첫 턴을 포함해 자신의 턴에 원하는 상대를 지목할 수 있다.

이번에 형진이가 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을 출력한다.

제한

힌트