You have a permutation $p$ of $N$ integers. Initially $p_i = i$ holds for $1 \leq i \leq N$. For each $j$ ($1 \leq j \leq N$), let's denote $p_{j}^0 = j$ and $p_{j}^k = p_{p_j}^{k-1}$ for any $k\geq 1$. The *period* of $p$ is defined as the minimum positive integer $k$ which satisfies $p_{j}^k = j$ for every $j$ ($1 \leq j \leq N$).

You are given $Q$ queries. The $i$-th query is characterized by two distinct indices $x_i$ and $y_i$. For each query, swap $p_{x_i}$ and $p_{y_i}$ and then calculate the period of updated $p$ modulo $10^9 + 7$ in the given order.

It can be proved that the period of $p$ always exists.

The input consists of a single test case of the following format.

$N$ $Q$ $x_1$ $y_1$ ... $x_Q$ $y_Q$

The first line consists of two integers $N$ and $Q$ ($2 \leq N \leq 10^5, 1 \leq Q \leq 10^5$). The ($i+1$)-th line consists of two integers $x_i$ and $y_i$ ($1 \leq x_i, y_i \leq N, x_i \ne y_i$).

Print the answer in one line for each query.

5 4 2 5 2 4 1 3 1 2

2 3 6 5

$p$ changes as follows: $[1,2,3,4,5] \rightarrow [1,5,3,4,2] \rightarrow [1,4,3,5,2] \rightarrow [3,4,1,5,2] \rightarrow [4,3,1,5,2]$.

2 2 1 2 1 2

2 1

$p$ changes as follows: $[1,2] \rightarrow [2,1] \rightarrow [1,2]$.

10 10 5 6 5 9 8 2 1 6 8 1 7 1 2 6 8 1 7 4 8 10

2 3 6 4 6 7 12 7 8 9

Source: ACM-ICPC Japan Alumni Group Summer Camp 2017
, Tokyo, Japan, 2017-09-24

http://acm-icpc.aitea.net/

http://acm-icpc.aitea.net/