# Topic

Because this competition ran into a problem, I used my memory to write this problem slowly. (what we did on site is really strong

Let's consider to build the edge from 1 to n first. If there are already n-1 black or white edges, then the output will be direct.

Otherwise, there is a point where both sides are black and white.

You can directly ask the edge of the point connecting the two sides and directly build this edge. Then you can go to the current point no matter whether it is a white tree or a black tree outside.

Next, we take the two points next to this point and search deeply. If the two points next to one of them are not connected, it must be a black edge and a white edge. Then we keep asking until they are connected.

In this process, we can use the linked list to maintain the left and right points.

```#include<map>
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;

int n,m,tot1,tot2;
map<pair<int,int>,int> f;
long long X,Y,Z;
long long p[500010];
int w[500010],b[500010];
struct edge{
int x,y;
}blk[500010],wht[500010];
int las[500010],nex[500010];

if(f[make_pair(a,b)]) return f[make_pair(a,b)];
if((min(a,b)*X+max(a,b)*Y)%Z<(p[a]+p[b])) return 2;
else return 1;
}

int findpa(int*f,int x){
if(f[x]!=x) return f[x]=findpa(f,f[x]);
return x;
}

void update(int x,int y,int t){
if(t==1) b[findpa(b,x)]=findpa(b,y),blk[++tot1]=(edge){x,y};
else w[findpa(w,x)]=findpa(w,y),wht[++tot2]=(edge){x,y};
}

bool insame(int x,int y){
int fx=findpa(w,x),fy=findpa(w,y);
if(fx==fy) return true;
fx=findpa(b,x);fy=findpa(b,y);
if(fx==fy) return true;
return false;
}

void dfs(int l,int r){
}

int main(){
scanf("%d %d",&n,&m);
int x,y,c;
for(int i=1;i<=m;i++){
scanf("%d %d %d",&x,&y,&c);
if(c==0) c=2;
f[make_pair(x,y)]=c;f[make_pair(y,x)]=c;
}
scanf("%lld %lld %lld",&X,&Y,&Z);
for(int i=1;i<=n;i++) scanf("%lld",&p[i]);
for(int i=1;i<=n;i++) b[i]=w[i]=i;
las[1]=n;for(int i=2;i<=n;i++) las[i]=i-1;
nex[n]=1;for(int i=1;i<n;i++) nex[i]=i+1;
if(tot1>=n-1) for(int i=1;i<=n-1;i++) printf("%d %d\n",blk[i].x,blk[i].y);
else if(tot2>=n-1) for(int i=1;i<=n-1;i++) printf("%d %d\n",wht[i].x,wht[i].y);
if(tot1>=n-1 || tot2>=n-1) return 0;
for(int i=1;i<=n;i++){
if(insame(las[i],nex[i])) continue;