The Amestris government has been alerted of cities, numbered to . However, they are going to be slowly reopening roads, at a steady rate of road per day, for days to . knows their plan, and will only move between two cities if he knows that they are in the same strangely connected component. He will ask queries in the form "", asking the first day on which and will be strangely connected, or if it will never be strangely connected.

’s plan, and has decided to shut down all bidirectional roads between its**Note:** We define a strangely connected component as a connected component that will not be disconnected by removing any 1 edge.

#### Input Specification

First line:

Next lines: integers and , representing that cities and are connected on the -th day.

Next lines: integers and , representing a query.

#### Subtasks

For full points,

For 5/25 points,

#### Sample Input

```
4 5 3
3 3
1 3
3 0
3 2
2 3
0 2
3 3
0 3
```

#### Sample Output

```
-1
0
-1
```

## Comments

There appears to be test cases where a == N or b == N, despite the cities being numbered from 0 to N - 1.

(deleted)