#include using namespace std; typedef long long int uli; const int mx=1e5+10; const int mxq=5e5+10; //vector operations struct pt{ uli x,y; pt(){} pt(uli x,uli y):x(x),y(y){} pt operator +(pt a){return pt(x+a.x, y+a.y); } pt operator -(pt a){return pt(x-a.x, y-a.y); } pt operator *(uli k){return pt(x*k,y*k); } uli operator *(pt a){ return x*a.y-y*a.x; } uli operator %(pt a){ return x*a.x+y*a.y; } uli d2(){ return x*x+y*y; } double d(){ return sqrt(d2()); } bool operator <(pt a)const{ if(y!=a.y)return yadj[mx];//adj[i]={j: there is a fence i->j} bool hidden[mx+mx];//hidden[i]=was fence i removed? pairg[mx+mx];//g[i]=triangles sharing diagonal i map,int>diagonals;//diagonals[{i,j}]=index of the fence joining vertices i,j map,int>triangles;//triangles[{i,j,k}])index of the region delimited by vertices i,j,k vectorvtriangles[mx];//vtriangles[i]=vertices of triangle i in clockwise order struct edge{ int to,x,y,nxt; bool operator <(edge e)const{ return totree[mx]; int base; int n; int idx(int i,int j,int k){//get index of triangle with vertices i,j,k vectorijk={i,j,k}; vectormini=ijk;//lexicographically smallest rotation for(int it=0;it<3;it++){ swap(ijk[0],ijk[1]); swap(ijk[1],ijk[2]); mini=min(mini,ijk); } auto t=make_tuple(mini[0],mini[1],mini[2]); if(triangles.count(t)==0){ int sz=triangles.size(); triangles[t]=sz; vtriangles[sz].resize(3); for(int it=0;it<3;it++){ vtriangles[sz][it]=farm[mini[it]]; } } return triangles[t]; } bool cmp(int i,int j){//comparator for diagonals that go out from a given vertex return (i-base+n)%n<(j-base+n)%n; } vectorall; int sz[mx]; bool vis[mx]; int p[mx]; vectornxt[mx]; void dfs(int u){ all.push_back(u); sz[u]=1; for(auto e:tree[u]){ int v=e.to; if(!vis[v] && v!=p[u]){ p[v]=u; dfs(v); sz[u]+=sz[v]; } } } int centroidDec(int u){ all.clear(); p[u]=u; dfs(u); int cen=-1; for(int x:all){ bool ok=true; for(auto e:tree[x]){ int y=e.to; if(!vis[y]){ int szy=sz[y]; if(y==p[x])szy=sz[u]-sz[x]; //szy<=szu/2 if(szy+szy>sz[u]){ ok=false; break; } } } if(ok){ cen=x; break; } } vis[cen]=true; for(int i=0;it){//t is clockwise for(int i=0;i<3;i++)if((p-t[i])*(t[(i+1)%3]-t[i])<=0)return false; return true; } int onDiag,onTriangle; void find(int u,pt p){ if(pointInTriangle(p,vtriangles[u])){ onTriangle=u; return; } for(auto e:tree[u]){ int v=e.nxt; if(v==-1)continue; pt a=farm[e.x]; pt b=farm[e.y]; if(pointInSegment(p,a,b) && p!=a && p!=b){ onDiag=diagonals[{e.x,e.y}]; return; } if((p-a)*(b-a)>0){//point is at the right find(v,p); return; } } } int main(){ // freopen("secret/1.in","r",stdin); // freopen("secret/1.out","w",stdout); int tc; scanf("%d",&tc); while(tc--){ int q; scanf("%d %d",&n,&q); for(int i=0;i0); // cout<<"triangle "<"<w must exist if(diagonals.count({v,w})==0){ adj[v].push_back(w); adj[w].push_back(v); diagonals[{v,w}]=nd; diagonals[{w,v}]=nd++; qs[q++]={1,v,w}; } bef=t; } } assert(nd==n+n-3); assert(int(triangles.size())==n-2); for(int i=0;i"<=0;i--){ if(qs[i].op==1){ int d=diagonals[{qs[i].x,qs[i].y}]; hidden[d]=true; join(g[d].first,g[d].second);//merge triangles } else{ onDiag=-1; onTriangle=-1; find(cen,{qs[i].x,qs[i].y}); if(onTriangle==-1 && onDiag==-1)ans[i]=0; else if(onTriangle!=-1){ int u=gp(onTriangle); ans[i]=area[u]; } else{ if(hidden[onDiag])ans[i]=area[gp(g[onDiag].first)]; else ans[i]=0; } } } for(int i=0;i