24677번 - 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.