设每个点的权值为和它相连的所有边的权值的异或和，那么等价于选若干个点，使得点权异或和最大，这显然只需要维护一组线性基，然后从高位到低位贪心选取即可。

对于本题，因为有修改操作，所以考虑按时间分治，并用bitset加速，时间复杂度$O(\frac{m\log mL^2}{64})$。

针对插入操作，可以用Four Russian Method进一步优化。

将$1000$个基$4$个一组分成$250$组，每组对于$2^4$种可能的插入向量预处理出消元后的结果。

那么插入只需要$250$次消元，插入之后重新预处理那块即可。

时间复杂度$O(\frac{m\log mL^2}{64\log L})$。

 

#include
     
      #include
      
       #include
       
        #include
        
         #define N 505using namespace std;typedef bitset<1000>bs;int n,m,i,x,y,cnt,vis[N],cur,idb[N],idg[N];bs B[1000],fin,w,a[N],q[2010],pb[N];struct P{int l,r,p;P(int _l,int _r,int _p){l=_l,r=_r,p=_p;}};vector
         
V;struct Block{  bs a[16];int b[16];  void build(int x){    for(int S=1;S<16;S++){      int j;      for(j=3;~j;j--)if(S>>j&1)break;      if(B[x+3-j][x+3-j]){        a[S]=B[x+3-j];        int ret=S;        for(int i=j;~i;i--)if(B[x+3-j][x+3-i])ret^=1<
          
           x){ B[idb[cur]]=pb[cur]; G[idg[cur]]=pg[cur]; cur--; }}void solve(int l,int r,vector
          
         
V){  int t=cur;  vector
         
S;  for(vector
         
::iterator it=V.begin();it!=V.end();it++)    if(it->l<=l&&r<=it->r)ins(q[it->p]);    else S.push_back(*it);  if(l==r){    fin.reset();    for(int i=0;i<1000;i++)if(!fin[i])if(B[i][i])fin^=B[i];    bool flag=0;    for(int i=0;i<1000;i++)if(fin[i])putchar('1'),flag=1;else if(flag)putchar('0');    if(!flag)putchar('0');    puts("");    retrace(t);    return;  }  int mid=(l+r)>>1;  solve(l,mid,S),solve(mid+1,r,S);  retrace(t);}int main(){  scanf("%d",&n);  scanf("%d%d",&n,&m);  for(i=1;i<=m;i++){    scanf("%d%d",&x,&y);    get();    x--,y--;    if(vis[x])q[++cnt]=a[x],V.push_back(P(vis[x],i-1,cnt));    if(vis[y])q[++cnt]=a[y],V.push_back(P(vis[y],i-1,cnt));    vis[x]=vis[y]=i;    a[x]^=w,a[y]^=w;  }  for(i=0;i