레이팅 미적용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.
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.
Subtask 1 (11 points): n, \(m \le 20\)
Subtask 2 (41 points): There exists a street connecting a park to itself which is not patrolled by a cat
Subtask 3 (68 points): No additional constraints.
The first line contains integers \(n\), \(m\) (\(1 \le n \le 2 \cdot 10^{4}\), \(0 \le m \le 2 \cdot 10^{4}\)), number of parks and cats.
The following \(n\) lines contain pairs a, b (\(1 \le a\), \(b \le 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 \le x\), \(y \le 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.
In the first and only line, output the length of the shortest possible Cat Tour or “−1” if no Cat Tours
exist.
5 1
3 1
3 2
3 4
3 5
2 4
3 526 7
3 2
5 3
1 4
6 1
5 6
4 2
4 5
1 2
4 2
2 6
3 1
1 6
6 4107 3
4 1
4 3
6 4
2 6
5 2
5 7
4 4
3 6
4 1
7 5-1Clarification of the first example:
The shortest Cat Tour is 3 →5 →3.