Скоро Codeforces Round 1133 (Div. 1, Div. 2)! Регистрация здесь. ×

I. Incredible XORlandia
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

XORlandia is a city on the coast of Northeastern Brazil, famous for its crystal-clear beaches, its enormous waterfront, and its slogan XORlandia is massa. Legend says that, during the construction of the city, an old fisherman known as Old Sururu cursed some of the region's streets after losing a dominoes match to a local resident.

Since then, each street in the city has had an energy, represented by an integer associated with it. The city has $$$N$$$ tourist spots numbered from $$$1$$$ to $$$N$$$; spot $$$1$$$ is Marco dos XORais and spot $$$N$$$ is where the XORgante Chair is located. They are connected by $$$M$$$ bidirectional streets. The $$$i$$$-th street connects spots $$$U_i$$$ and $$$V_i$$$ and has energy $$$W_i$$$. It is also known that it is possible to reach any spot from any other, and that there is at most one street connecting each pair of spots.

As a local tradition, residents define the value of a path as the XOR of the energies of all streets traversed. A path may pass through the same spot and traverse the same street multiple times. Each time a street is traversed, its energy is included again in the XOR calculation, even if that same street has already been used earlier in the path. The city hall considers XORlandia an incredible city if every path that starts at Marco dos XORais and ends at the XORgante Chair has value equal to $$$0$$$.

Therefore, the city hall decided that it may choose exactly one street and change its energy to any other non-negative integer value, as long as it is different from the previous value.

For each street, determine whether it is possible to change only the value of that street so that the city becomes incredible.

Input

The first line contains two integers $$$N$$$ and $$$M$$$, indicating respectively the number of tourist spots in XORlandia and the number of streets.

Each of the next $$$M$$$ lines contains three integers $$$U_i$$$, $$$V_i$$$, and $$$W_i$$$ $$$(1 \leq U_i, V_i \leq N,\ U_i \neq V_i,\ 0 \leq W_i \lt 2^{30})$$$, representing a bidirectional street connecting spots $$$U_i$$$ and $$$V_i$$$, with energy $$$W_i$$$.

  • $$$2 \leq N \leq 200000$$$
  • $$$N - 1 \leq M \leq \min\left(\frac{N(N-1)}{2}, 200000\right)$$$
Output

Print a binary string of length $$$M$$$.

The $$$i$$$-th character must be:

  • 1, if it is possible to modify only the $$$i$$$-th street so that XORlandia becomes incredible;
  • 0, otherwise.
Examples
Input
5 5
1 2 1
1 3 0
3 4 0
2 4 2
4 5 3
Output
01100
Input
3 2
1 2 127
2 3 127
Output
00
Input
3 2
1 2 127
2 3 128
Output
11
Note

Explanation for example 1

In the first example, it is possible to change the energy of the second or third street so that every path from spot $$$1$$$ to spot $$$5$$$ has value $$$0$$$. None of the other streets allows this condition to be achieved with a single change. Therefore, the answer is 01100.

Explanation for example 2

In the second example, the path from spot $$$1$$$ to spot $$$3$$$ has value $$$127 \oplus 127 = 0$$$. However, since it is mandatory to change the energy of exactly one street to a different value, it is impossible to keep this value equal to $$$0$$$. Therefore, the answer is 00.

Explanation for example 3

In the third example, one may change the energy of the first street to $$$128$$$ or the energy of the second street to $$$127$$$. In either choice, the path from spot $$$1$$$ to spot $$$3$$$ has value $$$0$$$. Therefore, the answer is 11.