C. Неисправный Поток
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Эмускальд считает себя мастером алгоритмов по нахождению потока. Он только что завершил самую искусную из всех своих программ: она вычисляет максимальный поток в неориентированном графе. Граф состоит из n вершин и m ребер. Вершины пронумерованы от 1 до n. Вершины 1 и n — исток и сток, соответственно.

Однако, его алгоритм максимального потока, похоже, немного неисправен: для каждого ребра он находит только величину потока, протекающего по этому ребру, но не направление, в котором течет поток. Помогите ему для каждого ребра найти направление, в котором должен протекать поток по этому ребру, чтобы в итоге получился корректный максимальный поток.

Более формально: дан неориентированный граф, в котором для каждого неориентированного ребра (ai, bi) задана величина ci. Вы должны ориентировать все ребра так, чтобы выполнялись следующие условия:

  1. для каждой вершины v (1 < v < n), сумма ci входящих ребер равняется сумме ci исходящих ребер;
  2. вершина номер 1 не имеет входящих ребер;
  3. полученный ориентированный граф не имеет циклов.
Входные данные

Первая строка входных данных содержит два целых числа через пробел n и m (2 ≤ n ≤ 2·105, n - 1 ≤ m ≤ 2·105), количество вершин и ребер в графе. Каждая из следующих m строк содержит три целых числа ai, bi и ci (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ ci ≤ 104) через пробел, которые обозначают неориентированное ребро от ai до bi, по которому протекает в некотором направлении ci единиц потока.

Гарантируется, что не существует двух ребер, соединяющих одни и те же вершины; данный граф связный; решение всегда существует.

Выходные данные

Выведите m строк, в каждой строке должно быть по целому числу di, равному 0, если направление i-го ребра равняется ai → bi (поток протекает от вершины ai к вершине bi), и равному 1 в противном случае. Считайте, что ребра пронумерованы от 1 до m в том порядке, в котором они заданы во входных данных.

Если существует несколько решений, выведите любое из них.

Примеры
Входные данные
3 3
3 2 10
1 2 10
3 1 5
Выходные данные
1
0
1
Входные данные
4 5
1 2 10
1 3 10
2 3 5
4 2 15
3 4 5
Выходные данные
0
0
1
1
0
Примечание

В первом тестовом примере 10 единиц потока проходят по пути , а 5 единиц потока проходят прямо от истока к стоку: .