Доктор Стрэндж владеет оком Агамотто, плащом левитации, а также n магическими сферами. Между некоторыми сферами существует фантомная связь. Доктору необходимо зарядить каждую сферу темной или светлой магией для восстановления баланса сил.
Всего существует m пар связанных сфер, при этом каждая связь обладает определенной силой e. Пусть r — это сумма по всем силам связи. Баланс сил считается успешно восстановленным, если суммарная сила связи между сферами, заряженными одним типом магии, не больше, чем r / 2.
Помогите Стрэнджу найти правильный тип магии для каждой сферы.
В первой строке заданы числа n и m — количество сфер и количество связей (1 ≤ n, m ≤ 105).
Далее следуют m строк. В каждой записаны числа a, b и e — связь между сферой a и b с силой равной e (1 ≤ a, b ≤ n; 1 ≤ e ≤ 109).
Гарантируется, что сферы не связаны сами с собой и не существует более одной связи между каждой парой сфер.
Если ответ существует, требуется вывести n чисел, где i-ое число равно 1, если сфера i заряжена темной магией, либо i-ое число равно 0, если сфера i заряжена светлой магией. Если ответа не существует, выведите Nema.
3 2
1 2 2
2 3 3
0 0 1
5 6
1 2 1
2 3 1
3 4 5
5 1 2
2 5 2
3 1 3
0 1 1 0 0
В первом примере значение r = 5 и сумма ребер одного цвета равна 2. Раскраска подходит, потому что сумма ребер одного цвета 2 меньше, чем половина суммы всех ребер 2.5.