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

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

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

Ограничения

2 ≤ N ≤ 105, 1 ≤ M ≤ 105

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 5
1 2
2 3
3 1
3 4
2 4
1 1.5 1.5 1

Разбор

Вычислим степень каждой вершины графа di. Пусть d0 = minidi. Положим pi = di / d0. Нетрудно проверить, что по каждому ребру графа в обе стороны переносится одинаковое количество продуктов, поэтому количество продуктов в каждом муравейнике со временем не меняется.

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

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

(i,j)∈ Epjdj − pi = 0.

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

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


0.131s 0.022s 13