Minimum Cycle Covering Directed Cat‐Edges

You are given a graph with n nodes and n+m edges. Among these, n edges are undirected and it is guaranteed that if you keep only these undirected edges, the graph remains connected. Note that the undirected edges may include multiple edges and self–loops.

In addition, there are m directed edges. Each of these directed edges has a cat on it. The directed edges may have multiple copies but there are no self–loops.

Everyone loves cats, so you want to take a stroll such that your route (a cycle) passes through every directed edge exactly once. Moreover, each edge (directed or undirected) can be traversed at most once. (Note: traversing the same undirected edge in both directions counts as using it twice, and is not allowed.)

Your task is to find a legal cycle with the minimum possible length. The length of a cycle is the total number of edges used (each edge counts as 1, regardless of type). If no such cycle exists, output -1.

Input Format: The first line contains two integers n and m. The next n lines each contain two integers representing the endpoints of an undirected edge. The following m lines each contain two integers representing the start and end vertices of a directed edge.

Output Format: Output a single integer, the minimum cycle length that uses every directed edge exactly once (and any undirected edge at most once), or -1 if no legal cycle exists.

inputFormat

The first line contains two integers: n and m, representing the number of nodes and the number of directed edges (in addition to the n undirected edges).
Each of the next n lines contains two integers u v representing an undirected edge between nodes u and v (self-loops and multiple edges possible).
Each of the following m lines contains two integers u v representing a directed edge from node u to node v (multiple edges may exist; self-loops do not occur).

outputFormat

Output a single integer, the minimum cycle length meeting the problem conditions, or -1 if no valid cycle exists.

sample

3 2
1 2
2 3
3 1
1 2
2 3

4