Эмускальд считает себя мастером алгоритмов по нахождению потока. Он только что завершил самую искусную из всех своих программ: она вычисляет максимальный поток в неориентированном графе. Граф состоит из n вершин и m ребер. Вершины пронумерованы от 1 до n. Вершины 1 и n — исток и сток, соответственно.
Однако, его алгоритм максимального потока, похоже, немного неисправен: для каждого ребра он находит только величину потока, протекающего по этому ребру, но не направление, в котором течет поток. Помогите ему для каждого ребра найти направление, в котором должен протекать поток по этому ребру, чтобы в итоге получился корректный максимальный поток.
Более формально: дан неориентированный граф, в котором для каждого неориентированного ребра (ai, bi) задана величина ci. Вы должны ориентировать все ребра так, чтобы выполнялись следующие условия:
- для каждой вершины v (1 < v < n), сумма ci входящих ребер равняется сумме ci исходящих ребер;
- вершина номер 1 не имеет входящих ребер;
- полученный ориентированный граф не имеет циклов.
Выходные данные
Выведите m строк, в каждой строке должно быть по целому числу di, равному 0, если направление i-го ребра равняется ai → bi (поток протекает от вершины ai к вершине bi), и равному 1 в противном случае. Считайте, что ребра пронумерованы от 1 до m в том порядке, в котором они заданы во входных данных.
Если существует несколько решений, выведите любое из них.
Примечание
В первом тестовом примере 10 единиц потока проходят по пути 
, а 5 единиц потока проходят прямо от истока к стоку: 
.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
3 2 10
1 2 10
3 1 5
|
1
0
1
|
|
2
|
4 5
1 2 10
1 3 10
2 3 5
4 2 15
3 4 5
|
0
0
1
1
0
|