This is an approximate problem.

Hackerland and Coderland are two countries which share a border with each other. There are a total of N cities in these two countries. The capital of Hackerland is city A and the capital of Coderland is city B. The President of these two countries are dedicated towards the welfare of their citizens. Due to strange climate conditions, city A is suffering from water scarcity. Also, due to rapid development in city B, all the animals have fled away and they are facing huge milk scarcity.

They signed a pact and decided to help each other. There is a network of pipes established between cities (including the two capital cities A and B) where $i^{th}$ pipe is installed between cities $U_{i}$ and $V_{i}$ having capacity $C_{i}$ and liquid flow direction from $U_{i}$ to $V_{i}$. Note that there can be multiple pipes between two cities. It should be ensured that the products both cities deliver to each other must be pure, i.e, there should be no mixing of these two products in the pipes. In other words, each pipe should either carry milk or water, not both. Also, each city acts as a junction which has two separate reservoirs which ensures that there is no mixing of the products at any junction point.

Since the Presidents of both cities are very generous and each of them wants to provide the other with resources at maximum rate, they call you to design the network in such a way that the total sum of rate at which the resources are provided to each other is maximum possible.

For each pipe $P_{i}$, you are allowed to do one of the following operations:

• Use the pipe for transporting milk from A to B.
• Use the pipe for transporting water from B to A.
• Keep it unused.

Please help the people of city A and B as they are suffering from scarcity of these resources.

For each pipe $P_{i}$, output 0 if it is unused, 1 if it is used for transporting milk and 2 if it is used for transporting water.

Input Format:

The first line of input contains N and M which denotes the number of cities and the number of pipes in the network respectively. City A is 1 and City B is N.

The next M lines contains three space separated integers $U_{i}$, $V_{i}$ and $C_{i}$ representing pipe $P_{i}$. This denotes that there is a pipe from $U_{i}$ to $V_{i}$ having capacity $C_{i}$.

Output Format:

Output M space separated integers where $i^{th}$ integer denotes the configuration of pipe $P_{i}$. Each of these integers can take values either 0, 1 or 2 as described in the problem statement.

Scoring:

Let F and $TotalCapacity$ be your final maximum rate at which resources are shared and the sum of capacities of all the edges for a certain test case . The final score for this test will be $(F / TotalCapacity) * 10^5$.

Constraints:

$1 \le N \le 2000$

$1 \le M \le 5000$

$1 \le C_i \le 5000$

$1 \le U_i, V_i \le 2000$

$U_i \ne V_i$

Test Case Generation:

Test cases have been generated using the following code:

#include<bits/stdc++.h>
using namespace std;

int main() {
  srand(time(NULL));
  int n = rand()%2000 + 1; // n - number of cities
  int m = rand()%5000 + 1; // m - number of pipes
  printf("%d %d\n", n, m);
  int cnt = 0;
  while(cnt != m) {
    int u, v, c;
    u = rand()%n + 1;
    v = rand()%n + 1;
    c = rand()%5000 + 1;   // c - capacity
    if(u != v) {
      printf("%d %d %d\n", u, v, c);
      cnt ++;
    }
  }
  return 0;
}