Загадан массив целых чисел $$$a_1, a_2, \ldots, a_n$$$.
Сам массив неизвестен, но известно $$$m$$$ утверждений вида $$$a_x + a_y = s$$$.
Гарантируется, что все утверждения не противоречат друг другу, то есть существует хотя бы один целочисленный массив, удовлетворяющий всем ограничениям.
Для некоторых индексов значение $$$a_i$$$ может определяться однозначно, а для некоторых — нет.
Требуется вывести все индексы $$$i$$$, для которых значение $$$a_i$$$ можно восстановить однозначно, а также сами значения $$$a_i$$$.
В первой строке входных данных содержатся два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — размер массива и количество утверждений соответственно.
В каждой из следующих $$$m$$$ строк входных данных содержатся по три целых числа $$$x$$$, $$$y$$$ и $$$s$$$ ($$$1 \le x, y \le n$$$, $$$1 \le s \le 10^9$$$). Каждая такая строка задаёт утверждение $$$a_x + a_y = s$$$.
Гарантируется, что все утверждения не противоречат друг другу.
В первой строке выведите целое число $$$k$$$ — количество индексов, для которых значение элемента массива определяется однозначно.
В следующих $$$k$$$ строках выведите по два целых числа $$$i$$$ и $$$a_i$$$ — индекс элемента массива и его однозначно восстановленное значение.
Пары $$$(i, a_i)$$$ необходимо выводить в порядке возрастания индексов $$$i$$$.
5 41 2 72 3 91 3 84 5 10
3 1 3 2 4 3 5
7 61 2 72 3 51 3 183 4 144 5 76 7 20
5 1 10 2 -3 3 8 4 6 5 1
Если существует несколько различных целочисленных массивов, удовлетворяющих всем утверждениям, но значение $$$a_i$$$ одинаково во всех таких массивах, то считается, что $$$a_i$$$ можно восстановить однозначно.
Рассмотрим первый пример из условия. Первые три утверждения задают систему уравнений относительно $$$a_1, a_2, a_3$$$: $$$a_1+a_2=7$$$, $$$a_2+a_3=9$$$ и $$$a_1+a_3=8$$$. Отсюда можно однозначно восстановить, что $$$a_1=3$$$, $$$a_2=4$$$ и $$$a_3=5$$$.
Последнее утверждение задаёт только сумму $$$a_4+a_5=10$$$, поэтому значения $$$a_4$$$ и $$$a_5$$$ по отдельности определить нельзя. В частности, подошли бы варианты: $$$a_4=1$$$, $$$a_5=9$$$ или $$$a_4=2$$$, $$$a_5=8$$$.