Cat Tour

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

The Tourist Center has decided to open a Cat Tour in Zagreb. A tour starts at a park, pets every cat in Zagreb, and returns to the starting park, so tourists can repeat it. To keep tourists from getting lost, the Tourist Center puts up a sign in each street telling tourists which street to take next. Therefore a tour cannot use the same street twice, not even in opposite directions. Tourists expect to pet every cat, expect no cat to attack them, and want the tour to be as short as possible.

Help the Tourist Center by finding the length of the shortest possible Cat Tour, or report that no tour is possible.

The first line contains integers $n$ and $m$ ($1 \le n \le 2 \cdot 10^4$, $0 \le m \le 2 \cdot 10^4$), the number of parks and cats.

The next $n$ lines each contain a pair $a$, $b$ ($1 \le a, b \le n$) describing a street without a cat. A street may connect a park to itself, and several streets may connect the same pair of parks.

The next $m$ lines each contain a pair $x$, $y$ ($1 \le x, y \le n$) describing a street with a cat that allows passage from $x$ to $y$. Several streets may connect the same pair of parks.

Output the length of the shortest Cat Tour on one line, or $-1$ if no Cat Tour exists.

The shortest Cat Tour in the first example is 3 → 5 → 3.