#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<unordered_set>
#include"collapse.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
#define mad(a,b) a=(a+b)%mod
//namespace solver1{
vi g[5010];
bool vis[5010];
void dfs(ll x){
if(vis[x])return ;
vis[x]=1;
for(auto y:g[x])dfs(y);
}
vi simulateCollapse(int N,vi T,vi X,vi Y,vi W,vi P){
int C=T.size(),Q=W.size();
for(int i=0;i<C;i++){
if(X[i]>Y[i])swap(X[i],Y[i]);
}
vi FANS(Q);
for(int i=0;i<Q;i++){
for(int j=0;j<N;j++){
g[j].clear();
vis[j]=0;
}
unordered_set<ll> S;
for(int j=0;j<=W[i];j++){
ll key=X[j]*5010+Y[j];
if(S.count(key))S.erase(key);
else S.insert(key);
}
for(auto key:S){
ll x=key/5010,y=key%5010;
if(not(x<=P[i]&&P[i]+1<=y)){
g[x].push_back(y);
g[y].push_back(x);
}
}
ll cnt=0;
for(int j=0;j<N;j++){
if(vis[j])continue;
dfs(j);
cnt++;
}
FANS[i]=cnt;
}
return FANS;
}
//};
/*int main(){
ll N,C,Q;
cin>>N>>C>>Q;
vi T(C),X(C),Y(C),W(Q),P(Q);
rep(i,C){
cin>>T[i]>>X[i]>>Y[i];
}
rep(i,Q){
cin>>W[i]>>P[i];
}
vi ANS1=solver1::simulateCollapse(N,T,X,Y,W,P);
for(auto t:ANS1)cout<<t<<endl;
}*/
