Restricted Arrays

Time limit4sMemory limit256 MB

Summary

Count the moduli M up to n for which some integer array satisfies a[x]+1 = a[y] (mod M) for every given pair, and list them.

Level: Hard8 of 10
Topics: Graph, Union-find, Number theory, Math
Solved: No attempts yet

Problem

Let $n$ be a positive integer. Find the number of integers $M$ with $1 \le M \le n$ for which there exists an array of integers $a[1..n]$ satisfying the following conditions: $a[x_i] + 1 \equiv a[y_i] \pmod{M}, \quad 1 \le i \le q$

Input

The first line contains two integers, $n$ and $q$ : the array size and the number of conditions ( $1\le n, q \le 10^6$ ).

Each of the next $q$ lines contains two integers, $x_i$ and $y_i$ : the indices describing the corresponding condition ( $1 \le x_i, y_i \le n$ ).

Output

On the first line, print an integer $t$ : the number of possible values of $M$ . On the second line, print the $t$ possible values of $M$ in increasing order.

Examples4

Example 1
Input
```
3 3
1 2
2 3
3 1
```
Expected output
```
2
1 3
```
Example 2
Input
```
5 5
1 2
2 3
3 4
4 5
1 5
```
Expected output
```
2
1 3
```
Example 3
Input
```
5 5
1 2
2 3
3 1
4 5
5 4
```
Expected output
```
1
1
```
Example 4
Input
```
5 1
1 2
```
Expected output
```
5
1 2 3 4 5
```