Game of Death (Easy)

Interview

Time limit1sMemory limit1024 MB

Summary

Given a directed graph where each person points at two others, find a K from 10 to 99 such that a walk of K steps from person 1 never ends back at person 1.

Level: Medium4 of 10
Topics: Graph, BFS
Solved: No attempts yet

Problem

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

(Yeah~) It's fun (yeah~) and even more fun, Game of Death! (Bam-bam)

At the last 'death' or 'bam' of the intro chant, all participants point at a random person with a finger. Then the host calls any number, and counting starts from the host's finger, moving to the person being pointed at, one number per person. This repeats. (Source: Namu Wiki)

Hyungjin plays a drinking game with N people, including himself. When the game starts, every participant receives a number from 1 to N and points at one other person with the left hand and one other person with the right hand. A person may point at the same person twice.

After pointing, participant 1 says a positive integer K with $10 \le K \le 99$ . 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 also 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 drinks.

Everyone, including Hyungjin, is drunk. On their turn, each person passes the turn at random to one of the two people they pointed at. If both hands pointed at the same person, the turn goes to that person. Hyungjin and everyone else cannot know in advance who they will pass the turn to.

Hyungjin receives number 1 this time, so he gets to choose K. Given who each person pointed at, choose a suitable K so that Hyungjin never loses. If Hyungjin can lose no matter which K is chosen, print -1.

Input

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

Each of the next N lines contains $L_i$ and $R_i$ , separated by a space. These are the numbers of the people that participant i pointed at with the left and right hand. $(1 \le L_i, R_i \le N,$ $L_i \neq i,$ $R_i \neq i)$

Output

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

Examples3

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
```
Example 3
Input
```
3
2 3
3 1
1 2
```
Expected output
```
-1
```