题目

问题描述

这是一道经典傻逼题，对经典题很熟悉的人也不要激动，希望大家不要傻逼。

考虑一张$n$个点的带权无向图，点的编号为$1$到$n$。对于图中的任意一个点集（可以为空或者全集），所有恰好有一个端点在这个点集中的边组成的集合被称为割。一个割的权值被定义为所有在这个割上的边的异或和。

一开始这张图是空图，现在，考虑给这张无向图不断的加边，加入每条边之后，你都要求出当前权值最大的割的权值，注意加入的边永远都不会消失。

输入格式

从文件shabiti.in中读入数据。

输入的第一行包括一个数$id$表示数据编号，如第一组数据中的$id = 1$。注意样例数据中的$id = 0$。

接下来的第一行包括两个整数$n, m$表示图的点数和总共加的边。

接下来$m$行，每行三个正整数$x, y, w$表示在点$x$和点$y$之间加入一条权值为$w$的边。注意$x$和$y$可能相同，两条不同的边也可能连接了同一对点。

此外，$w$将以二进制形式从高位向低位给出，比如，$6 = 110_2$，因此如果边权为$6$，那么$w$将会是$110$。

输出格式

输出到shabiti.out中。

输出$m$行，按顺序输出每一条边加入之后权值最大的割的权值。

同样，你也要以二进制形式输出，形式和输入格式中描述的形式一样。

样例输入 1

0
3 6
1 2 1
1 2 1
3 3 111
1 3 101101
1 2 1011
2 3 111011

样例输出 1

1
0
0
101101
101101
110000

样例说明 1

前三条边加入之后的答案较为显然，考虑后三条边，加入第六条边之前，考虑点集$\{1,2\}$，它对应的割只有第四条边，因此答案就是第四条边的权值，考虑加入最后一条边以后的情况，此时点集$\{1,2\}$对应的割变成了第四条边和第六条边组成的集合，权值也发生了相应的改变。点集$\{2\}$对应的割是第五条边和第六条边组成的集合，可以证明这就是权值最大的割，权值为$1011_2 \oplus 111011_2 = 110000_2$。

样例输入输出 2

见下发的shabiti/shabiti1.in与shabiti/shabiti1.ans。

样例说明 2

这组数据满足最终形成的图中每个点的度数不超过$1$。

样例输入输出 3

见下发的shabiti/shabiti2.in与shabiti/shabiti2.ans。

数据规模和约定

设$l = \log_{2}w$。

对于所有数据，$1 \leq n \leq 500$，$1 \leq m \leq 1000$，$0 \leq l < 1000$，$1 \leq x, y \leq n$。