brute force dp math

If Bob is winning for given $$$n$$$ stones then Alice will win for $$$n + 2$$$ stones and $$$n + 3$$$ stones, because in $$$n + 2$$$ case Alice will remove $$$2$$$ stones and in $$$n + 3$$$ case Alice will remove $$$3$$$ stones resulting in $$$n$$$ stones where players switch their turns i.e., now Bob will play like first player for these $$$n$$$ stones, so obviously Alice will win.

From this information we can create $$$dp$$$ table, where $$$dp[x]$$$ refers who will win if pile contains $$$x$$$ stones. The base case is for $$$n = 1$$$ where Bob will win.

So from this $$$dp$$$ table , if Alice is already winning no need to add stones , otherwise we will iterate untill we reach the state where Alice will win.

If we observe the pattern, it will look like LWWWLLWWWLLWWWLLWWWLL... where $$$L$$$ means Alice loosing, $$$W$$$ means Alice winning. we can easily see from the pattern that if $$$n$$$ mod $$$5 \ge 2$$$ no need to add stones, Otherwise answer will be $$$2 - n$$$ mod $$$5$$$.

Time Complexity : $$$O(t)$$$

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int r=(n%5);
        if(r==0) cout<<"2\n";
        else if(r==1) cout<<"1\n";
        else cout<<"0\n";
    }
}

constructive algorithm implementation

The Upperbound value of $$$k$$$ for given $$$n$$$ is $$$⌈ \frac{n}{2} ⌉^2$$$, because the top-left square grid containing $$$⌈ \frac{n}{2} ⌉^2$$$ cells can have any characters which will mirror the other cells.

There are many ways to construct the grid, the below implementation is one of them.

Time Complexity : $$$O(n^2)$$$

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        int maxi=((n+1)/2)*((n+1)/2);
        if(k>maxi) cout<<"-1\n";
        else{
            vector<vector<int>> v(n,vector<int>(n));
            int val=0;
            for(int i=0;i<(n+1)/2;i++){
                for(int j=0;j<(n+1)/2;j++){
                    v[i][j]=val;
                    v[i][(n-j-1)]=val;
                    val=(val+1)%k;
                }
            }
            int x=1;
            if(n%2) x++;
            for(int i=(n+1)/2;i<n;i++){
                for(int j=0;j<n;j++){
                    v[i][j]=v[i-x][j];
                }
                x+=2;
            }
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    cout<<(char)('a'+v[i][j]);
                }
                cout<<"\n";
            }
        }
    }
}

number theory math

General idea of the solution is to store the count of the factors of all $$$a_i(1 \le i \le n)$$$, in that the answer is the maximum factors whose count is greater than or equal to $$$n-2$$$, because we can change the remaining elements to this factor. But this solution is too slow. Infact we don't need to calculate all elements factors, it is sufficient to calculate any $$$3$$$ elements factors. Because if you are interested in any $$$4$$$-th element factors then if those factor is not included in the previous $$$3$$$ elements choosen then its not useful because we can only change upto maximum $$$2$$$ elements.

Note that we can actually also solve this problem by taking factors of only $$$1$$$ element, below implementation shows this.

Time Complexity : $$$O(nD(x)+t \sqrt{x})$$$, where $$$x$$$ is any element from $$$a$$$, $$$D(x)$$$ means number of factors of $$$x$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
vector<ll> get(ll n){
    vector<ll> v;
    for(ll i=1;i*i<=n;i++){
        if(n%i==0){
            v.push_back(i);
            ll j=(n/i);
            if(j!=i) v.push_back(j);
        }
    }
    return v;
}
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        vector<ll> a(n);
        ll ans=0;
        for(ll i=0;i<n;i++){
            cin>>a[i];
            ans=__gcd(ans,a[i]);
        }
        sort(a.begin(),a.end());
        vector<ll> v=get(a[0]);
        for(ll i=0;i<(ll)v.size();i++){
            ll cnt=0;
            for(ll j=0;j<n;j++) if(a[j]%v[i]==0) cnt++;
            if(cnt>=(n-2)) ans=max(ans,v[i]);
        }
        vector<ll> p,s;
        for(ll i=1;i<n;i++) p.push_back(a[i]);
        s=p;
        for(ll i=1;i<(ll)p.size();i++) p[i]=__gcd(p[i],p[i-1]);
        for(ll i=(ll)s.size()-2;i>=0;i--) s[i]=__gcd(s[i],s[i+1]);
        for(ll i=0;i<(ll)p.size();i++){
            ll val=0;
            if(i-1>=0) val=__gcd(val,p[i-1]);
            if(i+1<(ll)s.size()) val=__gcd(val,s[i+1]);
            ans=max(ans,val);
        }
        ll val=0;
        for(ll i=2;i<n;i++) val=__gcd(val,a[i]);
        ans=max(ans,val);
        cout<<ans<<"\n";
    }
}

data structure greedy

Let's first solve the problem for the entire array. Consider the prefix sum array $$$S$$$, where we want all $$$S[i] > 0$$$.

Consider how a swap operation would change the $$$S$$$ array. Clearly, we only pick $$$a[i] = -1$$$ and $$$a[j] = 1$$$. This makes $$$S[i, \dots, j-1]$$$ increase by 2.

Thus, we have a greedy strategy: each time, select the smallest $$$i$$$ and the largest $$$j$$$ such that $$$a[i] = -1$$$ and $$$a[j] = 1$$$. Let $$$\text{minS} = \min(S[1, \dots, n])$$$. With each operation, $$$\text{minS}$$$ increases by 2, so the required number of operations is easy to calculate.

Returning to the original problem, we can use a segment tree to maintain $$$S$$$. For operation 2, this is simply a range addition operation on the segment tree. For operation 1, we can easily find the $$$\text{minS}$$$ for each interval.

Time Complexity : $$$O(nlogn)$$$

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);

vector<ll> tree,lazy,v1;

void build(ll v, ll tl, ll tr){
    if(tl==tr) tree[v]=v1[tl];
    else{
        ll m=(tl+tr)/2;
        build(2*v+1,tl,m);
        build(2*v+2,m+1,tr);
        tree[v]=min(tree[2*v+1],tree[2*v+2]);
    }
}

void push(ll v){
    tree[2*v+1]+=lazy[v];
    tree[2*v+2]+=lazy[v];
    lazy[2*v+1]+=lazy[v];
    lazy[2*v+2]+=lazy[v];
    lazy[v]=0;
}

ll get(ll v, ll tl, ll tr, ll l, ll r){
    if(l>r) return 1e18;
    if(l==tl && r==tr) return tree[v];
    push(v);
    ll m=(tl+tr)/2;
    ll val1=get(2*v+1,tl,m,l,min(r,m));
    ll val2=get(2*v+2,m+1,tr,max(l,m+1),r);
    return min(val1,val2);
}

void update(ll v, ll tl, ll tr, ll l, ll r, ll x){
    if(l>r) return;
    if(l==tl && r==tr){
        tree[v]+=x;
        lazy[v]+=x;
    }
    else{
        push(v);
        ll m=(tl+tr)/2;
        update(2*v+1,tl,m,l,min(r,m),x);
        update(2*v+2,m+1,tr,max(l,m+1),r,x);
        tree[v]=min(tree[2*v+1],tree[2*v+2]);
    }
}
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll n,q;
        cin>>n>>q;
        vector<ll> a(n);
        for(ll i=0;i<n;i++) cin>>a[i];
        v1.clear();
        v1=a;
        for(ll i=1;i<n;i++) v1[i]+=v1[i-1];
        tree.clear();
        tree.resize(4*n);
        lazy.clear();
        lazy.resize(4*n);
        build(0,0,n-1);
        while(q--){
            ll type;
            cin>>type;
            if(type==1){
                ll l,r;
                cin>>l>>r;
                l--;
                r--;
                ll sum=get(0,0,n-1,r,r);
                if(l-1>=0) sum-=get(0,0,n-1,l-1,l-1);
                if(sum<=0) cout<<"-1\n";
                else{
                    ll val=get(0,0,n-1,l,r);
                    if(l-1>=0) val-=get(0,0,n-1,l-1,l-1);
                    if(val>0) cout<<"0\n";
                    else{
                        val=-val;
                        cout<<(val+2)/2<<"\n";
                    }
                }
            }
            else{
                ll pos;
                cin>>pos;
                pos--;
                if(a[pos]==1) update(0,0,n-1,pos,n-1,-2);
                else update(0,0,n-1,pos,n-1,2);
                a[pos]*=-1;
            }
        }
    }
}

constructive algorithm tree

There will be no tree if the grid $$$a$$$ doesn't satisfy atleast one of the following condition :

1. $$$a_{ij} = a_{ji}$$$
2. $$$a_{ii}=i$$$
3. $$$a_{ij} \le a_{(a_{ij})j}$$$

Otherwise we can construct the tree in many ways, one of the possible way is:

1. Lets create a parent array $$$par$$$ where $$$par[x]$$$ denotes the parent of node $$$x$$$, initially $$$par[i]=-1$$$ for every $$$i(1 \le i \le n)$$$.

2. we will iterate for $$$x = 1, 2, 3, \cdots , n$$$ in this order and for every $$$y(1 \le y \le n)$$$ we will update $$$par[y] = x$$$ if $$$a_{xy}=x$$$.

Time Complexity : $$$O(n^2)$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector<vector<int>> v(n,vector<int>(n));
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cin>>v[i][j];
                v[i][j]--;
            }
        }
        bool ok=true;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(i==j && v[i][j]!=i) ok=false;
                if(v[i][j]!=v[j][i]) ok=false;
                if(v[i][j]>min(i,j)) ok=false;
                if(i<j){
                    if(v[i][j]!=v[v[i][j]][j]) ok=false;
                }
            }
        }
        if(ok){
            vector<int> par(n,0);
            par[0]=-1;
            for(int i=1;i<n;i++){
                for(int j=0;j<n;j++){
                    if(i!=j && v[i][j]==i) par[j]=i;
                }
            }
            for(int i=1;i<n;i++){
                cout<<par[i]+1<<" "<<i+1<<"\n";
            }
        }
        else cout<<"-1\n";
    }
}

dp tree

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);

ll mod=1e9+7;

long long power(long long a,long long b){
  long long x=1,y=a;
  while(b>0){
    if(b&1ll){
      x=(x*y)%mod;
    }
    y=(y*y)%mod;
    b>>=1;
  }
  return x%mod;
}
 
long long modular_inverse(long long n){
  return power(n,mod-2);
}

#define MAXN 2000005
 
long long factorial[MAXN];
long long invfact[MAXN];
 
void cfact(){
  long long i;
  factorial[0]=1;
  factorial[1]=1;
  for(i=2;i<MAXN;i++){
    factorial[i]=factorial[i-1]*i;
    factorial[i]%=mod;
  }
  invfact[MAXN-1]=modular_inverse(factorial[MAXN-1]);
  for(i=MAXN-2;i>=0;i--){
    invfact[i]=invfact[i+1]*(i+1);
    invfact[i]%=mod;
  }
}
 
long long calcnCr(long long n,long long k){
  if(k<0 || n<k){return 0;}
  return (factorial[n]*((invfact[k]*invfact[n-k])%mod))%mod;
}

vector<vector<ll>> adj,dp;
vector<ll> sz,dp1,v1;
ll xx,yy;

void dfs(ll x, ll p){
    dp[x][0]=1;
    for(auto i:adj[x]){
        if(i!=p){
            dfs(i,x);
            for(ll j=0;j<=sz[x]+sz[i];j++) dp1[j]=0;
            for(ll j=0;j<=sz[x];j++){
                for(ll k=1;k<=sz[i];k++){
                    dp1[j+k]=(dp1[j+k]+(((dp[x][j]*dp[i][k])%mod)*calcnCr(j+k-v1[x]-v1[i],j-v1[x]))%mod)%mod;
                }
            }
            sz[x]+=sz[i];
            v1[x]+=v1[i];
            for(ll j=0;j<=sz[x];j++){
                dp[x][j]=dp1[j];
            }
        }
    }
    sz[x]++;
    for(ll j=0;j<=sz[x];j++) dp1[j]=0;
    for(ll j=0;j<sz[x];j++){
        dp1[j+1]=(dp1[j+1]+(dp[x][j]*(j+1-v1[x]))%mod)%mod;
        dp1[j]=(dp1[j]+(dp[x][j+1]*j)%mod)%mod;
        dp1[j]=(dp1[j]+(dp[x][j]*(2*j-v1[x]))%mod)%mod;
    }
    for(ll j=0;j<=sz[x];j++){
        dp[x][j]=dp1[j];
    }
}
 
int main(){
    fast;
    cfact();
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        adj.clear();
        adj.resize(n);
        for(ll i=0;i<n-1;i++){
            ll u,v;
            cin>>u>>v;
            u--;
            v--;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        dp.clear();
        dp.resize(n+2);
        for(ll i=0;i<n+2;i++) dp[i].resize(n+2);
        dp1.clear();
        dp1.resize(n+2);
        sz.clear();
        sz.resize(n+2);
        v1.clear();
        v1.resize(n+2);
        dfs(0,-1);
        cout<<dp[0][1]<<"\n";
    }
}

data structure

#include<iostream>
#include<vector>
#include<tuple>
#include<unordered_map>
#include<unordered_set>
#include<functional>
#include<assert.h>
using namespace::std;
using lint=long long;
#define rep(i,n) for(lint i=0;(i)<lint(n);(i)++)
template<typename T>
class dynamic_connectivity{
	class euler_tour_tree{
		public:
		struct node;
		using np=node*;
		using lint=long long;
		struct node{
			np ch[2]={nullptr,nullptr};
			np p=nullptr;
			int l,r,sz,sz2;
			T val=et,sum=et;
			bool exact=1;
			bool child_exact;
			bool edge_connected=0;
			node(){}
			node(int l,int r):l(l),r(r),sz(l==r),sz2(0),child_exact(l<r){}
			bool is_root() {
				return !p;
			}
		};
		vector<unordered_map<int,np>>ptr;
		np get_node(int l,int r){
			if(ptr[l].find(r)==ptr[l].end())ptr[l][r]=new node(l,r);
			return ptr[l][r];
		}
		np root(np t){
			if(!t)return t;
			while(t->p)t=t->p;
			return t;
		}
		bool same(np s,np t){
			if(s)splay(s);
			if(t)splay(t);
			return root(s)==root(t);
		}
		np reroot(np t){
			auto s=split(t);
			return merge(s.second,s.first);
		}
		pair<np,np> split(np s){
			splay(s);
			np t=s->ch[0];
			if(t)t->p=nullptr;
			s->ch[0]=nullptr;
			return {t,update(s)};
		}
		pair<np,np> split2(np s){
			splay(s);
			np t=s->ch[0];
			np u=s->ch[1];
			if(t)t->p=nullptr;
			s->ch[0]=nullptr;
			if(u)u->p=nullptr;
			s->ch[1]=nullptr;
			return {t,u};
		}
		tuple<np,np,np> split(np s,np t){
			auto u=split2(s);
			if(same(u.first,t)){
				auto r=split2(t);
				return make_tuple(r.first,r.second,u.second);
			}else{
				auto r=split2(t);
				return make_tuple(u.first,r.first,r.second);
			}
		}
		template<typename First, typename... Rest>
		np merge(First s,Rest... t){
			return merge(s,merge(t...));
		}
		np merge(np s,np t){
			if(!s)return t;
			if(!t)return s;
			while(s->ch[1])s=s->ch[1];
			splay(s);
			s->ch[1]=t;
			if(t)t->p=s;
			return update(s);
		}
		int size(np t){return t?t->sz:0;}
		int size2(np t){return t?t->sz2:0;}
		np update(np t){
			t->sum=et;
			if(t->ch[0])t->sum=fn(t->sum,t->ch[0]->sum);
			if(t->l==t->r)t->sum=fn(t->sum,t->val);
			if(t->ch[1])t->sum=fn(t->sum,t->ch[1]->sum);
			t->sz=size(t->ch[0])+(t->l==t->r)+size(t->ch[1]);
			t->sz2=size2(t->ch[0])+(t->edge_connected)+size2(t->ch[1]);
			t->child_exact=(t->ch[0]?t->ch[0]->child_exact:0)|(t->l<t->r&&t->exact)|(t->ch[1]?t->ch[1]->child_exact:0);
			return t;
		}
		// void push(np t){
		// 	//遅延評価予定
		// }
		void rot(np t,bool b){
			np x=t->p,y=x->p;
			if((x->ch[1-b]=t->ch[b]))t->ch[b]->p=x;
			t->ch[b]=x,x->p=t;
			update(x);update(t);
			if((t->p=y)){
				if(y->ch[0]==x)y->ch[0]=t;
				if(y->ch[1]==x)y->ch[1]=t;
				update(y);
			}
		}
		void splay(np t){
			//push(t);
			while(!t->is_root()){
				np q=t->p;
				if(q->is_root()){
					//push(q), push(t);
					rot(t,q->ch[0]==t);
				}else{
					np r=q->p;
					//push(r), push(q), push(t);
					bool b=r->ch[0]==q;
					if(q->ch[1-b]==t)rot(q,b),rot(t,b);
					else rot(t,1-b),rot(t,b);
				}
			}
		}
		void debug(np t){
			if(!t)return;
			debug(t->ch[0]);
			cerr<<t->l<<"-"<<t->r<<" ";
			debug(t->ch[1]);
		}
		constexpr static T et=T();
		constexpr static T fn(T s,T t){
			return s+t;
		}
		public:
		euler_tour_tree(){}
		euler_tour_tree(int sz){
			ptr.resize(sz);
			for(int i=0;i<sz;i++)ptr[i][i]=new node(i,i);
		}
		int size(int s){
			np t=get_node(s,s);
			splay(t);
			return t->sz;
		}
		bool same(int s,int t){
			return same(get_node(s,s),get_node(t,t));
		}
		void set_size(int sz){
			ptr.resize(sz);
			for(int i=0;i<sz;i++)ptr[i][i]=new node(i,i);
		}
		void update(int s,T x){
			np t=get_node(s,s);
			splay(t);
			t->val=fn(t->val,x);
			update(t);
		}
		void edge_update(int s,function<void(int,int)> g){
			np t=get_node(s,s);
			splay(t);
			function<void(np)>dfs=[&](np t){
				assert(t);
				if(t->l<t->r&&t->exact){
					splay(t);
					t->exact=0;
					update(t);
					g(t->l,t->r);
					return;
				}
				if(t->ch[0]&&t->ch[0]->child_exact)dfs(t->ch[0]);
				else dfs(t->ch[1]);
			};
			while(t&&t->child_exact){
				dfs(t);
				splay(t);
			}
		}
		bool try_reconnect(int s,function<bool(int)> f){
			np t=get_node(s,s);
			splay(t);
			function<bool(np,int)>dfs=[&](np t,int idx)->bool{
				assert(t);
				if(t->edge_connected&&(size2(t->ch[0])==idx)){
					splay(t);
					return f(t->l);
				}
				if(idx<size2(t->ch[0]))return dfs(t->ch[0],idx);
				else return dfs(t->ch[1],idx-size2(t->ch[0])-(t->edge_connected));
			};
			while(size2(t)){
				if(dfs(t,0))return 1;
				splay(t);
			}
			return 0;
		}
		void edge_connected_update(int s,bool b){
			np t=get_node(s,s);
			splay(t);
			t->edge_connected=b;
			update(t);
		}
		bool link(int l,int r){
			if(same(l,r))return 0;
			merge(reroot(get_node(l,l)),get_node(l,r),reroot(get_node(r,r)),get_node(r,l));
			return 1;
		}
		bool cut(int l,int r){
			if(ptr[l].find(r)==ptr[l].end())return 0;
			np s,t,u;
			tie(s,t,u)=split(get_node(l,r),get_node(r,l));
			merge(s,u);
			np p=ptr[l][r];
			np q=ptr[r][l];
			ptr[l].erase(r);
			ptr[r].erase(l);
			delete p;delete q;
			return 1;
		}
		T get_sum(int p,int v){
			cut(p,v);
			np t=get_node(v,v);
			splay(t);
			T res=t->sum;
			link(p,v);
			return res;
		}
		T get_sum(int s){
			np t=get_node(s,s);
			splay(t);
			return t->sum;
		}
	};
	int dep=1;
	vector<euler_tour_tree> ett;
	vector<vector<unordered_set<int>>>edges;
	int sz;
	public:
	dynamic_connectivity(int sz):sz(sz){
		ett.emplace_back(sz);
		edges.emplace_back(sz);
	}
	bool link(int s,int t){
		if(s==t)return 0;
		if(ett[0].link(s,t))return 1;
		edges[0][s].insert(t);
		edges[0][t].insert(s);
		if(edges[0][s].size()==1)ett[0].edge_connected_update(s,1);
		if(edges[0][t].size()==1)ett[0].edge_connected_update(t,1);
		return 0;
	}
	bool same(int s,int t){
		return ett[0].same(s,t);
	}
	int size(int s){
		return ett[0].size(s);
	}
	vector<int>get_vertex(int s){
		return ett[0].vertex_list(s);
	}
	void update(int s,T x){
		ett[0].update(s,x);
	}
	T get_sum(int s){
		return ett[0].get_sum(s);
	}
	bool cut(int s,int t){
		if(s==t)return 0;
		for(int i=0;i<dep;i++){
			edges[i][s].erase(t);
			edges[i][t].erase(s);
			if(edges[i][s].size()==0)ett[i].edge_connected_update(s,0);
			if(edges[i][t].size()==0)ett[i].edge_connected_update(t,0);
		}
		for(int i=dep-1;i>=0;i--){
			if(ett[i].cut(s,t)){
				if(dep-1==i){
					dep++;
					ett.emplace_back(sz);
					edges.emplace_back(sz);
				}
				return !try_reconnect(s,t,i);
			}
		}
		return 0;
	}
	bool try_reconnect(int s,int t,int k){
		for(int i=0;i<k;i++){
			ett[i].cut(s,t);
		}
		for(int i=k;i>=0;i--){
			if(ett[i].size(s)>ett[i].size(t))swap(s,t);
			function<void(int,int)> g=[&](int s,int t){ett[i+1].link(s,t);};
			ett[i].edge_update(s,g);
			function<bool(int)> f=[&](int x)->bool{
				for(auto itr=edges[i][x].begin();itr!=edges[i][x].end();){
					auto y=*itr;
					itr=edges[i][x].erase(itr);
					edges[i][y].erase(x);
					if(edges[i][x].size()==0)ett[i].edge_connected_update(x,0);
					if(edges[i][y].size()==0)ett[i].edge_connected_update(y,0);
					if(ett[i].same(x,y)){
						edges[i+1][x].insert(y);
						edges[i+1][y].insert(x);
						if(edges[i+1][x].size()==1)ett[i+1].edge_connected_update(x,1);
						if(edges[i+1][y].size()==1)ett[i+1].edge_connected_update(y,1);
					}else{
						for(int j=0;j<=i;j++){
							ett[j].link(x,y);
						}
						return 1;
					}
				}
				return 0;
			};
			if(ett[i].try_reconnect(s,f))return 1;
		}
		return 0;
	}
};

vector<vector<lint>> adj;
vector<bool> vis;
bool ok1,ok2;
lint comp,sz;

void dfs(lint x){
    if(x%2) ok1=true;
    else ok2=true;
    vis[x]=true;
    sz++;
    for(auto i:adj[x]){
        if(!vis[i]) dfs(i);
    }
}

int main(){
    lint t;
    cin>>t;
    while(t--){
        lint n,q;
        cin>>n>>q;
        dynamic_connectivity<lint> dc(n+1);
        vector<lint> p(n+1);
        adj.clear();
        adj.resize(n+1);
        for(lint i=1;i<=n;i++){
            cin>>p[i];
            adj[i].push_back(p[i]);
            adj[p[i]].push_back(i);
            dc.link(i,p[i]);
            if(i%2) dc.update(i,1);
        }
        lint cnt1=0,cnt2=0;
        comp=0;
        vis.clear();
        vis.resize(n+1,false);
        for(lint i=1;i<=n;i++){
            if(!vis[i]){
                ok1=false;
                ok2=false;
                comp++;
                sz=0;
                dfs(i);
                if(ok1 && !ok2 && sz>1) cnt1++;
                if(!ok1 && ok2 && sz>1) cnt2++;
            }
        }
        cout<<(n-comp+2*(max(cnt1,cnt2)))<<" ";
        while(q--){
            lint x,y;
            cin>>x>>y;
            if(dc.same(x,y)){
                comp++;
                lint sum=dc.get_sum(x);
                lint siz=dc.size(x);
                if(sum==siz && siz>1) cnt1--;
                if(sum==0 && siz>1) cnt2--;
                dc.cut(x,p[x]);
                dc.cut(y,p[y]);
                dc.link(x,p[y]);
                dc.link(y,p[x]);
                sum=dc.get_sum(x);
                siz=dc.size(x);
                if(sum==siz && siz>1) cnt1++;
                if(sum==0 && siz>1) cnt2++;
                sum=dc.get_sum(y);
                siz=dc.size(y);
                if(sum==siz && siz>1) cnt1++;
                if(sum==0 && siz>1) cnt2++;
            }
            else{
                comp--;
                lint sum=dc.get_sum(x);
                lint siz=dc.size(x);
                if(sum==siz && siz>1) cnt1--;
                if(sum==0 && siz>1) cnt2--;
                sum=dc.get_sum(y);
                siz=dc.size(y);
                if(sum==siz && siz>1) cnt1--;
                if(sum==0 && siz>1) cnt2--;
                lint sz1=dc.size(x);
                if(sz1>2) dc.cut(x,p[x]);
                sz1=dc.size(y);
                if(sz1>2) dc.cut(y,p[y]);
                dc.link(x,p[y]);
                dc.link(y,p[x]);
                sum=dc.get_sum(x);
                siz=dc.size(x);
                if(sum==siz && siz>1) cnt1++;
                if(sum==0 && siz>1) cnt2++;
            }
            swap(p[x],p[y]);
            cout<<(n-comp+2*(max(cnt1,cnt2)))<<" ";
        }
        cout<<"\n";
    }
}