std::list 造福懒得写链表的入

#include <iostream>
#include <cstdio>
#include <cassert>
#include <list>
#include <memory.h>
using namespace std;
list <int> lst;
list <int>::iterator bucket[100005];//用桶存储每一个值的位置，因为链表查值是 O(n) 的，特慢
void solve(){
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		lst.push_back(i); 
	}
	for(pair <list <int>::iterator, int> tmp = {lst.begin(), 1};
	tmp.first != lst.end(); tmp.first++, tmp.second++){
		bucket[tmp.second] = tmp.first;
	}
	while(m--){
		char c;
		cin >> c;
		if(c == 'A'){//往左加
			int x, y;
			cin >> x >> y;
			lst.erase(bucket[x]);
			list <int>::iterator it = bucket[y];
			lst.insert(it, x);
			it--;
			bucket[x] = it;
		}
		if(c == 'B'){//往右加
			int x, y;
			cin >> x >> y;
			lst.erase(bucket[x]);
			list <int>::iterator it = bucket[y];
			it++;
			lst.insert(it, x);
			it--;
			bucket[x] = it;
		}
		if(c == 'Q'){//查询
			int tmp, val;
			cin >> tmp >> val;
			list <int>::iterator it = bucket[val];
			if(tmp == 0){
				if(it == lst.begin()) it = lst.end();//注意特判
				it--;
			}
			else{
				it++;
				if(it == lst.end()) it = lst.begin();
			}
			cout << (*it) << '\n';
		}
	}
	
	//记得清空！ 
	memset(bucket, 0, sizeof(bucket));
	lst.clear();
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while(t--) solve();

	return 0;
}