Game of Death (Hard)

Time limit1sMemory limit1024 MB

Summary

Pick K from 10 to 99 so Hyeongjin, who chooses his passes, never ends up holding the turn at K=0 while the others pass at random.

Level: Medium7 of 10
Topics: Game theory, Graph, BFS
Solved: No attempts yet

Problem

This problem differs from 'Game of Death (Easy)' in the conditions written in bold below.

(Yay~) So much fun (yay~) Game of Death is a blast! (Ba-bam)

At the last syllable of the intro chant, Death' or Ba'bam', all participants point at anyone with a finger at the same time. Then the host calls out any number. Counting starts from the host's finger and moves to the person being pointed at, one count per person, and this repeats. - Namu Wiki

Hyeongjin is playing a drinking game with $N$ people, including himself. When the game starts, every participant is given a number from $1$ to $N$ . Each person points at one other person with the left hand and one other person with the right hand, never at themselves. The same person may be pointed at twice.

After everyone has pointed, participant $1$ chooses a positive integer $K$ with $10 \leq K \leq 99$ and says it. Then participant $1$ decreases $K$ by $1$ and passes the turn to one of the people they pointed at. The person who receives the turn decreases $K$ by $1$ and passes the turn to one of the people they pointed at. This repeats until $K$ becomes $0$ . The person who receives the turn at that moment loses and must drink.

The other $N - 1$ people are all drunk. On their turn, each one passes the turn at random to one of the two people they pointed at (or to the single person, if they pointed at the same person twice). Those people cannot know whom they will pass to. Hyeongjin, who controlled his drinking, is not drunk, so on his own turns, including the first turn, he can point at whomever he wants.

Hyeongjin is participant $1$ and chooses $K$ . Given whom each person pointed at, find a $K$ so that Hyeongjin never loses when he plays his best. If Hyeongjin could lose for every choice of $K$ , print -1.

Input

The first line contains the number of participants $N$ . $(2 \leq N \leq 1\,000)$

The next $N$ lines describe whom each participant pointed at. On the $i$ -th line, $L_i$ and $R_i$ are the numbers of the people that participant $i$ pointed at with the left and right hand, separated by a space. $(1 \leq L_i, R_i \leq N, L_i \neq i, R_i \neq i)$

Output

Print a $K$ ( $10 \leq K \leq 99$ ) that satisfies the conditions of the problem. If no such $K$ exists, print -1.

Examples2

Example 1
Input
```
2
2 2
1 1
```
Expected output
```
11
```
Example 2
Input
```
5
2 3
4 5
4 5
2 3
2 3
```
Expected output
```
10
```