Description

fzx 有一个长度为 n 的初始 (a_i = i, 1 ≤ i ≤ n) 的数组,和长度为 m 的交换序列,他会按照序列顺序每次交换 2 个数

你需要准确地删除恰好一个交换操作,使得数字 1 最后交换到第 k 个位置,并输出需要删掉的交换操作的序号

如果有多个答案，输出序号最小的交换操作的序号

保证有解

Input Format

第一行 3 个正整数 n,m,k ,表示 n 个数, m 个交换，最终希望数字 1 交换到第 k 个位置

接下来 m 行每行 2 个数 a,b ,表示交换 a,b 位置上的数字

Output Format

样例一：
10 10 9
1 8
8 3
3 4
4 7
7 2
6 2
9 10
3 10
9 3
6 9
样例二：
10 10 2
1 3
3 4
4 1
1 5
3 7
7 9
3 6
4 3
10 8
5 2

样例一：
7</p>
样例二：
5

Hint

对于 $40$ %的数据 $n,m\le 1000$

对于另外 $30$ %的数据 保证不删除操作前经过m个操作,数字 $1$ 恰好交换到第 $k$ 个位置

对于 $100$ %的数据,$n,m\le 100000$

#include <stdio.h>
#include <iostream>
#define N 100005
using namespace std;
int n, m, k, ans, a[N], b[N], p[N], q[N];
int main() {
	//freopen("swap.in", "r", stdin);
	//freopen("swap.out", "w", stdout);
	int i, j;
	scanf("%d%d%d", &n, &m, &k);
	for(i = 1; i <= m; i++)
		scanf("%d%d", &a[i], &b[i]);
	p[0] = 1;
	for(i = 1; i <= m; i++) {
		p[i] = p[i-1];
		if(p[i] == a[i]) p[i] = b[i];
		else if(p[i] == b[i]) p[i] = a[i];
	}
	for(i = 1; i <= n; i++)
		q[i] = i;
	for(i = m; i; --i) {
		if(q[p[i-1]] == k) ans = i;
		swap(q[a[i]], q[b[i]]); 
	}
	printf("%d\n", ans);
	return 0;
}

Source