Задача E. Муравейники ≡

Условие

Как-то раз Марфа Геннадьевна пошла в лес по грибы с подружками. Грибники внимательно смотрели под ноги, чтобы не упустить ни одного хорошего гриба. Наклонившись за очередной сыроежкой, Марфа Геннадьевна заметила, что рядом был расположен целый муравьиный город — сеть муравейников, соединённых дорогами.

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

В каждом муравейнике всегда находится определённое количество продуктов. Это количество продуктов распределяется поровну между дорогами, ведущими из этого муравейника, и муравьи переносят продукты по дорогам. Количество продуктов в каждом муравейнике не меняется со временем, то есть суммарное количество продуктов, полученных данным муравейником, равняется суммарному количеству продуктов, отправленных из данного муравейника.

Грибники нарисовали схему муравейника и просят вас помочь обработать данные. Напишите программу для ответа на вопрос: какое количество продуктов может находиться в каждом муравейнике, чтобы выполнялись упомянутые закономерности? Количество продуктов в муравейнике с наименьшим количеством продуктов принять равным 1.

Формат входного файла

Входной файл содержит целые числа N M — количество муравейников и количество дорог. Далее следуют M пар целых чисел a_i b_i — номера муравейников, соединённых i-й дорогой. Дороги в этом списке не повторяются, и если в списке есть дорога a_i b_i, то нет дороги b_i a_i.

Из каждого муравейника можно добраться по дорогам до любого другого муравейника.

Формат выходного файла

Требуется вывести в выходной файл N вещественных чисел p_i — количества продуктов для каждого муравейника с точностью не менее 6 знаков после десятичной точки. Если решений несколько, выведите любое из них.

Ограничения

2 ≤ N ≤ 10⁵, 1 ≤ M ≤ 10⁵

Примеры тестов

4 5
1 2
2 3
3 1
3 4
2 4

1 1.5 1.5 1

Разбор

Вычислим степень каждой вершины графа d_i. Пусть d₀ = minid_i. Положим p_i = d_i / d₀. Нетрудно проверить, что по каждому ребру графа в обе стороны переносится одинаковое количество продуктов, поэтому количество продуктов в каждом муравейнике со временем не меняется.

Для вычисления степеней вершин графа не нужно сохранять граф в памяти в виде списков смежности. Достаточно считать рёбра из файла и для каждого ребра a_i b_i прибавить единицу к d[a_i] и d[b_i].

Интересно поставить вопрос о единственности решения данной задачи. Условия равенства входящего и исходящего количества продуктов для каждой вершины графа приводят к системе линейных уравнений:

∑(i,j) ∈ Ep_jd_j − p_i = 0.

Нетрудно видеть, что система имеет нулевое решение, а также ненулевое решение, приведённое выше. Тогда все точки на прямой, проходящей через две эти точки, также будут решением системы. Если других решений системы нет, то решение задачи единственно с точностью до нормировки.

Можно положить p₁ = 1 и исключить одно уравнение из системы. Тогда получим систему из N − 1 уравнений с таким же количеством неизвестных, и остаётся проверить, будет ли определитель матрицы этой системы отличен от нуля.