Description

Input

第一行包含两个整数N和 M， 表示该无向图中点的数目与边的数目。 接下来M 行描述 M 条边，每行三个整数Si，Ti ，Di，表示 Si 与Ti之间存在 一条权值为 Di的无向边。 图中可能有重边或自环。

Output

仅包含一个整数，表示最大的XOR和（十进制结果）,注意输出后加换行回车。

Sample Input

5 7

1 2 2

1 3 2

2 4 1

2 5 1

4 5 3

5 3 4

4 3 2

Sample Output

6

HINT

Solution

首先这个答案肯定是由一条简单路径和几个环构成的。简单路径外的环，我们是可以想用就用的，因为我们可以走到环那里绕一圈再回到起点，这样除了那个环之外别的地方都没有受到影响。

怎么求出所有的环呢？其实就是$DFS$树所有的反祖边和树边构成的环，$DFS$一下就可以找出来了。

我们找出所有的环，再随便找一条$1$到$n$的简单路径，用简单路径的$xor$去在环的线性基里找最大就好了。

为什么随便找一条简单路径是对的呢？因为我们找出的所有环中，肯定有在简单路径上的，这样的话简单路径在异或上这些环后，就会变成一条新的简单路径，这样调整下来最后肯定能得到最优解。

Code

1 #include
     
       2 #include
      
        3 #define N (200009) 4 #define LL long long 5 using namespace std; 6  7 struct Edge{LL to,next,len;}edge[N<<1]; 8 LL n,m,u,v,l,cnt; 9 LL head[N],num_edge;10 LL d[N],Xor[N],Circle[N];11 bool vis[N];12 13 void add(LL u,LL v,LL l)14 {15     edge[++num_edge].to=v;16     edge[num_edge].len=l;17     edge[num_edge].next=head[u];18     head[u]=num_edge;19 }20 21 void Insert(LL x)22 {23     for (int i=62; i>=0; --i)24         if (x&(1ll<
       
        =0; --i)55         ans=max(ans,ans^d[i]);56     printf("%lld\n",ans);57 }