$N$개의 정수로 이루어진 순열 $p$가 있다. 처음에 $p_i = i$가 $1 \le i \le N$에 대해 성립한다. 각 $j$에 대해 $(1 \le j \le N)$, $p^0_j = j$이고, $p^k_j = p^{k-1}_{p_j}$는 모든 $k \ge 1$에 대해 성립한다고 정의한다. 순열 $p$의 주기는 모든 $j$에 대해 $p^k_j = j$를 만족하는 최소 양의 정수 $k$로 정의된다.
당신은 $Q$개의 쿼리를 받는다. 각 쿼리는 두 개의 서로 다른 인덱스 $x_i$와 $y_i$로 특징지어진다.
각 쿼리에 대해, $p_{x_i}$와 $p_{y_i}$를 교환한 후, 주어진 순서대로 업데이트된 $p$의 주기를 $10^9 + 7$로 나눈 나머지를 계산하여라.
$p$의 주기는 항상 존재한다는 것을 증명할 수 있다.
### 입력
입력은 다음 형식의 단일 테스트 케이스로 구성된다.
$$
\begin{array}{cc}
N & Q \\
x_1 & y_1 \\
\vdots & \vdots \\
x_Q & y_Q
\end{array}
$$
첫 번째 줄에는 두 개의 정수 $N$과 $Q$가 주어진다. ($2 \le N \le 10^5$, $1 \le Q \le 10^5$).
$(i+1)$-번째 줄에는 두 개의 정수 $x_i$와 $y_i$가 주어진다. ($1 \le x_i, y_i \le N$, $x_i \ne y_i$).
### 출력
각 쿼리를 한 줄에 출력하시오.
### 예제 입력 1
```
5 4
2 5
2 4
1 3
1 2
```
### 예제 출력 1
```
2
3
6
5
```
$p$는 다음과 같이 변경된다: $[1,2,3,4,5] \to [1,5,3,4,2] \to [1,4,3,5,2] \to [3,4,1,5,2] \to [4,3,1,5,2]$.
semillo0o 1년 전
# 순열의 주기
### 문제
$N$개의 정수로 이루어진 순열 $p$가 있다. 처음에 $p_i = i$가 $1 \le i \le N$에 대해 성립한다. 각 $j$에 대해 $(1 \le j \le N)$, $p^0_j = j$이고, $p^k_j = p^{k-1}_{p_j}$는 모든 $k \ge 1$에 대해 성립한다고 정의한다. 순열 $p$의 주기는 모든 $j$에 대해 $p^k_j = j$를 만족하는 최소 양의 정수 $k$로 정의된다.
당신은 $Q$개의 쿼리를 받는다. 각 쿼리는 두 개의 서로 다른 인덱스 $x_i$와 $y_i$로 특징지어진다.
각 쿼리에 대해, $p_{x_i}$와 $p_{y_i}$를 교환한 후, 주어진 순서대로 업데이트된 $p$의 주기를 $10^9 + 7$로 나눈 나머지를 계산하여라.
$p$의 주기는 항상 존재한다는 것을 증명할 수 있다.
### 입력
입력은 다음 형식의 단일 테스트 케이스로 구성된다.
$$
\begin{array}{cc}
N & Q \\
x_1 & y_1 \\
\vdots & \vdots \\
x_Q & y_Q
\end{array}
$$
첫 번째 줄에는 두 개의 정수 $N$과 $Q$가 주어진다. ($2 \le N \le 10^5$, $1 \le Q \le 10^5$).
$(i+1)$-번째 줄에는 두 개의 정수 $x_i$와 $y_i$가 주어진다. ($1 \le x_i, y_i \le N$, $x_i \ne y_i$).
### 출력
각 쿼리를 한 줄에 출력하시오.
### 예제 입력 1
```
5 4
2 5
2 4
1 3
1 2
```
### 예제 출력 1
```
2
3
6
5
```
$p$는 다음과 같이 변경된다: $[1,2,3,4,5] \to [1,5,3,4,2] \to [1,4,3,5,2] \to [3,4,1,5,2] \to [4,3,1,5,2]$.
### 예제 입력 2
```
2 2
1 2
1 2
```
### 예제 출력 2
```
2
1
```
$p$는 다음과 같이 변경된다: $[1,2] \to [2,1] \to [1,2]$.
### 예제 입력 3
```
10 10
5 6
5 9
8 2
1 6
8 1
7 1
2 6
8 1
7 4
8 10
```
### 예제 출력 3
```
2
3
6
4
6
7
12
7
8
9
```
*그대로 복사 해서 문제 메모에 붙이면 LaTeX 문법에 맞게 적용 됩니다.*
오류 있을 수도 있을 수도 있습니다. 가능한 원본 보시는걸 추천합니다.