tura — COCI CONTEST_#4
Task type: batch | Time limit: 0.5 s | Memory limit: 512 MB | Difficulty: 18
Algorithms: unicyclic graph, eulerian path, degree balancing, connectivity

# Task Tura Mačkica

Croatian Open Competition in Informatics
Round 4, January 15th 2025
0.5 seconds / 512 MiB / 120 points

Everyone knows that Zagreb has *n* parks, *m* cats and *n* + *m* streets which connect the parks. The cats are very territorial animals so in each street there is at most one cat. It patrols the street by viciously attacking everyone who travels in one direction of that street, but from the people who are travelling in the opposite direction it demands pets before it lets them through. The City of Zagreb, aware of this circumstance, has made sure that the citizens can reach any park from any other park using only *n* streets without cats.

![Cat Image](_page_0_Picture_4.jpeg)

The Tourist Center has decided to open a so called Cat Tour in Zagreb. The tours visitors will be able to pet every cat in Zagreb and return to the starting location so they can do it all over again. To make sure the tourists don't get lost the tourist center will put up signs in each street telling them which street they shoud take next, so the Cat Tour cannot travel the same street twice (not even in the opposite directions). Obviously, tourists expect to pet every single cat, that no cat attacks them and that the tour is as short as possible.

Help the tourist center by finding the length of the shortest possible Cat Tour or say that it is not possible.

## Input

The first line contains integers *n*, *m* (1 ≤ *n* ≤ 2 * 10<sup>4</sup>, 0 ≤ *m* ≤ 2 * 10<sup>4</sup>), number of parks and cats.

The following *n* lines contain pairs *a, b* (1 ≤ *a, b* ≤ *n*) which describe the streets without cats. Note that it is possible that *a* = *b* or that two or more streets connect the same parks.

The following *m* lines contain pairs *x, y* (1 ≤ *x, y* ≤ *n*) which describe the streets where a cat allows passage from *x* to *y*. Note that it is possible that two or more streets connect the same parks.

## Output

In the first and only line, output the length of the shortest possible Cat Tour or "-1" if no Cat Tours exist.

## Scoring

| Subtask | Points | Constraints                                                                 |
| :------ | :----- | :-------------------------------------------------------------------------- |
| 1       | 11     | *n, m* ≤ 20                                                               |
| 2       | 41     | There exists a street connecting a park to itself which is not patrolled by a cat |
| 3       | 68     | No additional constraints.                                                |

## Examples

| input | input | input |
| :---- | :---- | :---- |
| 5 1   | 6 7   | 7 3   |
| 3 1   | 3 2   | 4 1   |
| 3 2   | 5 3   | 4 3   |
| 3 4   | 1 4   | 6 4   |
| 3 5   | 6 1   | 2 6   |
| 2 4   | 5 6   | 5 2   |
| 3 5   | 4 2   | 5 7   |
|       | 4 5   | 4 4   |
| output| 1 2   | 3 6   |
| 2     | 4 2   | 4 1   |
|       | 2 6   | 7 5   |
|       | 3 1   |       |
|       | 1 6   | output|
|       | 6 4   | -1    |
|       | output|       |
|       | 10    |       |

## Clarification of the first example:

The shortest Cat Tour is 3 → 5 → 3.

Starter code: