The package for this problem was not updated by the problem writer or Codeforces administration after we've upgraded the judging servers. To adjust the time limit constraint, a solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then the value 800 ms will be displayed and used to determine the verdict.

Croc Champ 2012 - Final |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dfs and similar

*2200

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Cyclic Coloring

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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* ≤ 10^{5}), 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 *a*_{i} and *b*_{i} (1 ≤ *a*_{i}, *b*_{i} ≤ *n*), which means that the *i*-th arc goes from vertex *a*_{i} to vertex *b*_{i}.

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).

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

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.

A possible coloring of the graph is:

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

A possible coloring of the graph is:

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/01/2024 09:42:07 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|