Problem Description

Tenkaichi Institute is actively engaged in various activities as a research base for combinatorics. Recently, it seems that research on graphs with an infinite number of vertices is particularly popular.

You are given a positive integer $ N $ and $ M $ pairs of integers between $ 0 $ and $ N-1 $ inclusive, denoted as $(A_1, B_1), (A_2, B_2), \ldots, (A_M, B_M)$.

Consider an undirected graph with an infinite number of vertices, defined as follows:

• For any integer $ z $ (including negative integers), there exists exactly one vertex corresponding to it. This vertex is referred to as vertex $ z $. No vertex corresponds to more than one integer.
• For any two integers $i, k\ (1 \leq i \leq M)$, vertex $A_i + k \times N$ and vertex $B_i + (k + 1) \times N$ are directly connected by a single edge. No other edges exist.

(Refer to the images in the Sample Input and Output section for clarification)

Determine whether the number of connected components in this graph is finite, and if so, find that number.

Input Format

The input is provided from the standard input in the following format:

$ N $ $ M $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ : $ $ A_M $ $ B_M $

Output Format

If the number of connected components in the given graph is finite, output that number. If it is infinite, output $ -1 $ instead.

Sample Input and Output

Sample Input #1

2 2
0 0
1 0

Sample Output #1

1

Sample Input #2

2 2
0 1
1 0

Sample Output #2

2

Sample Input #3

3 2
0 1
2 1

Sample Output #3

-1

Sample Input #4

7 8
0 3
1 2
1 5
2 5
3 4
4 6
5 2
6 3

Sample Output #4

4

Notes/Hints

Constraints

• $1 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• $0 \leq A_i, B_i \leq N-1$
• All pairs $ (A_i, B_i) $ are distinct.

Partial Points

• A dataset worth 400 points satisfies the following:
• $1 \leq N \leq 1000$
• $1 \leq M \leq 1000$

Sample Explanation 1

By following the edges, any two vertices can be reached from one another. Therefore, the number of connected components in this graph is $ 1 $.

Sample Explanation 2

There are two connected components in the form of infinite lines.

Sample Explanation 3

There are an infinite number of connected components each consisting of 3 vertices.

见题面 Input 部分

见题面 Output 部分