You are given a directed graph G with n vertices and m arcs (multiple arcs and self-loops are allowed). You have to paint each vertex of the graph into one of the k (k ≤ n) colors in such way that for all arcs of the graph leading from a vertex u to vertex v, vertex v is painted with the next color of the color used to paint vertex u.

The colors are numbered cyclically 1 through k. This means that for each color i (i < k) its next color is color i + 1. In addition, the next color of color k is color 1. Note, that if k = 1, then the next color for color 1 is again color 1.

Your task is to find and print the largest possible value of k (k ≤ n) such that it's possible to color G as described above with k colors. Note that you don't necessarily use all the k colors (that is, for each color i there does not necessarily exist a vertex that is colored with color i).

Input

The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 105), denoting the number of vertices and the number of arcs of the given digraph, respectively.

Then m lines follow, each line will contain two space-separated integers ai and bi (1 ≤ ai, bi ≤ n), which means that the i-th arc goes from vertex ai to vertex bi.

Multiple arcs and self-loops are allowed.

Output

Print a single integer — the maximum possible number of the colors that can be used to paint the digraph (i.e. k, as described in the problem statement). Note that the desired value of k must satisfy the inequality 1 ≤ k ≤ n.

Examples

Input

4 4
1 2
2 1
3 4
4 3


Output

2


Input

5 2
1 4
2 5


Output

5


Input

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


Output

3


Input

4 4
1 1
1 2
2 1
1 2


Output

1

Note

For the first example, with k = 2, this picture depicts the two colors (arrows denote the next color of that color).

<image>

With k = 2 a possible way to paint the graph is as follows.

<image>

It can be proven that no larger value for k exists for this test case.

For the second example, here's the picture of the k = 5 colors.

<image>

A possible coloring of the graph is:

<image>

For the third example, here's the picture of the k = 3 colors.

<image>

A possible coloring of the graph is:

<image>
import java.io.*;
import java.util.*;

public class CyclicColoring {
    BufferedReader br;
    PrintWriter out;
    StringTokenizer st;
    boolean eof;
    ArrayList<Integer>[] g, gr;
    int[] color;
    static final int NON_VISITED = Integer.MAX_VALUE;

    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    int ans = 0;

    void dfs(int v, int cur) {
        color[v] = cur;
        for (int to : g[v]) {
            if (color[to] == NON_VISITED)
                dfs(to, cur + 1);
            else {
                int tmp = Math.abs(color[to] - (cur + 1));
                ans = gcd(ans, tmp);
            }
        }
        for (int to : gr[v]) {
            if (color[to] == NON_VISITED)
                dfs(to, cur - 1);
            else {
                int tmp = Math.abs(color[to] - (cur - 1));
                ans = gcd(ans, tmp);
            }
        }
    }

    void solve() throws IOException {
        int n = nextInt();
        int m = nextInt();
        g = new ArrayList[n];
        gr = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            g[i] = new ArrayList<Integer>();
            gr[i] = new ArrayList<Integer>();
        }

        for (int i = 0; i < m; i++) {
            int v1 = nextInt() - 1;
            int v2 = nextInt() - 1;
            g[v1].add(v2);
            gr[v2].add(v1);
        }

        color = new int[n];
        Arrays.fill(color, NON_VISITED);
        for (int i = 0; i < n; i++)
            if (color[i] == NON_VISITED)
                dfs(i, 0);
        out.println(ans == 0 ? n : ans);
    }

    void inp() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        solve();
        out.close();
    }

    public static void main(String[] args) throws IOException {
        new CyclicColoring().inp();
    }

    String nextToken() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                eof = true;
                return null;
            }
        }
        return st.nextToken();
    }

    String nextString() {
        try {
            return br.readLine();
        } catch (IOException e) {
            eof = true;
            return null;
        }
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
}