Restricted Arrays

Let $n$ be a positive integer. Find the number of integers $1 \le M \le n$ for which there exists an array of integers $a\[1..n]$ that satisfies the following conditions: $a\[x\_i] + 1 \equiv a\[y\_i] \pmod{M} , \quad 1 \le i \le q *.*$

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

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.