410048: GYM103931 J Just Some Bad Memory

Relax. Let me tell you in the fastest pace what you need to do.

Give you a simple graph $$$G = (V, E)$$$ consisting of undirected edges. You need to tell me, what is the minimum number of edges should you add to the graph, resulting a simple graph containing at least one odd cycle and at least one even cycle.

A simple graph is a graph without multiple edges and self-loops, which means that each edge connects two different vertices and no two edges connect the same pair of vertices.

A cycle is a sequence of distinct vertices $$$\{v_1, v_2, \dots, v_k\}$$$, such that $$$(v_{i}, v_{i \bmod k + 1}) \in E$$$. The odd or even describes the parity of $$$k$$$. A smallest odd cycle is of length $$$3$$$, and a smallest even cycle is of length $$$4$$$.

The first line contains two integers $$$n, m ~ (1 \leq n \leq 10 ^ 5, 0 \leq m \leq \min \left\{2 \times 10 ^ 5, {n \choose 2}\right\})$$$, denoting the number of vertices ($$$|V|$$$) and the number of edges ($$$|E|$$$).

In the next $$$m$$$ lines, each line contains two integers $$$u, v ~ (1 \leq u, v \leq n, u \neq v)$$$, denoting that there are edges connecting vertices $$$u$$$ and $$$v$$$.

It's guaranteed that the input graph is a simple graph.

Print one integer in a single line, denoting your answer. If the mission is impossible, print '-1' instead.

3 3
1 2
2 3
1 3

-1

4 0

5

5 4
1 2
2 3
3 4
4 5

2

4 6
1 2
1 3
1 4
2 3
2 4
3 4

0

4 4
1 2
2 3
3 4
4 1

1

7 7
1 2
2 3
3 4
4 1
5 6
6 7
7 5

0

Here is one possible solution of sample 2. The contained odd cycles are $$$\{1, 2, 3\}$$$ and $$$\{1, 3, 4\}$$$, and the only even cycle is $$$\{1, 2, 3, 4\}$$$.