题目
问题描述
这是一道经典傻逼题，对经典题很熟悉的人也不要激动，希望大家不要傻逼。
考虑一张$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$。
| 数据点 | $n$的规模 | $m$的规模 | $l$的规模 | 备注 |
| $1$ | $n \leq 20$ | $m \leq 50$ | $l < 32$ | |
| $2$ | $n \leq 20$ | $m \leq 50$ | $l < 32$ | |
| $3$ | $n \leq 200$ | $m \leq 100$ | $l < 100$ | 最终形成的图中每个点的度数不超过$1$，且没有自环。 |
| $4$ | $n \leq500$ | $m \leq 250$ | $l < 1000$ |
| $5$ | $n \leq500$ | $m \leq 250$ | $l < 1000$ |
| $6$ | $n \leq 100$ | $m \leq 200$ | $l < 300$ | |
| $7$ | $n \leq 100$ | $m \leq 200$ | $l < 300$ | |
| $8$ | $n \leq 500$ | $m \leq 1000$ | $l < 1000$ | |
| $9$ | $n \leq 500$ | $m \leq 1000$ | $l < 1000$ | |
| $10$ | $n \leq 500$ | $m \leq 1000$ | $l < 1000$ | |
对于所有数据，$1 \leq n \leq 500$，$1 \leq m \leq 1000$，$0 \leq l < 1000$，$1 \leq x, y \leq n$。
