Problem Statement

You are given a directed graph with $N$ vertices and $M$ edges. The $i$-th $(1\leq i\leq M)$ edge goes from vertex $U_i$ to vertex $V_i$. This edge is denoted by $(U_i,\ V_i)$. The graph may contain multiple edges and self-loops.

Consider a sequence of vertices $(v_i)\ (1\leq v_i\leq N)$, where repetition is allowed, and let $L$ be the length of $(v_i)$. When the edge $(v_i,\ v_{i+1})$ exists for every $i\ (1\leq i\leq L-1)$, we call the sequence $(v_1,\ (v_1,\ v_2),\ v_2,\ (v_2,\ v_3),\ v_3,\ \ldots,\ v_{L-1},\ (v_{L-1},\ v_L),\ v_L)$ a walk.

Ruel wants to add a finite number of directed edges to the given graph so that there exists a walk that passes through every edge exactly $1$ time.

That is, he wants to add $K$ edges $(U_{M+i},\ V_{M+i})\ (1\leq i\leq K)$ to obtain a directed graph with $N$ vertices and $(M+K)$ edges, such that there exists a permutation $(P_1,\ P_2,\ \ldots,\ P_{M+K})$ of $(1,\ 2,\ \ldots,\ M+K)$ for which $V_{P_i}=U_{P_{i+1}}$ holds for every $i\ (1\leq i\leq M+K-1)$ and the sequence $(U_{P_1},\ (U_{P_1},\ V_{P_1}),\ V_{P_1},\ (U_{P_2},\ V_{P_2}),\ V_{P_2},\ \ldots,\ V_{P_{M+K-1}},\ (U_{P_{M+K}},\ V_{P_{M+K}}),\ V_{P_{M+K}})$ is a walk.

If edges can be added in this way, print the minimum number of edges to add. If no walk passing through every edge exactly $1$ time exists no matter how edges are added, print -1.

Input

$N\ M$
$U_1\ V_1$
$U_2\ V_2$
$U_3\ V_3$
$\vdots$
$U_M\ V_M$

• All inputs are integers
• $1\leq N\leq 2\times 10^5$
• $1\leq M\leq 2\times 10^5$
• $1\leq U_i\leq N\ (1\leq i\leq M)$
• $1\leq V_i\leq N\ (1\leq i\leq M)$

Output

Print the minimum number of edges to add or -1, followed by a newline.

Sample

Sample 1

Input

4 7
1 2
1 3
1 4
2 1
3 1
3 4
4 2

Output

1

If you add an edge from vertex $2$ to vertex $3$, there exists a walk that passes through every edge exactly $1$ time.

This is illustrated below.

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

0

3 5
1 2
2 1
2 1
2 3
3 3

1

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

1