Импульсные сигналы

F Импульсные сигналы
Некоторая сеть связи содержит N  генераторов импульсных сигналов, в составе которых имеется
внутренний  счетчик.  Линии  связи  двунаправленные  и  между   двумя  генераторами  может быть
только одна линия связи. Изначально все генераторы выключены и их счетчики установлены в ноль.
Во включенном состоянии каждый генератор отправляет сигнал с интервалом в одну секунду всем
соседним генераторам в сети, если таковые имеются. Если к генератору приходит сигнал по линии
связи,  то его внутренний  счетчик увеличивается на единицу. Если генератор был выключен при
получении сигнала, то он включается и увеличивает свой счетчик на единицу, и через 1 секунду
рассылает свой первый сигнал. В момент времени 0 включается и отправляет свой первый сигнал
генератор номер 1. От вас требуется определить состояние счетчиков всех генераторов в момент
времени T (через T полных секунд, т.е. сигнал, прошедший на секунде T, считается обработанным).

Формат входных данных
Первая строка входного файла содержит целые числа N и M (1 ? N ? 100, 1 ? M ? 10000) – число
генераторов и число линий связи в сети. Следующие M строк содержат по два различных числа –
номера генераторов соединенных между собой в сети. Генераторы нумеруются от 1 до  N. Далее
следует целое число T (1 ? T ? 1000000000). Числа в строках разделены пробелами.

Формат выходных данных
Выходной файл должен содержать N разделенных пробелами чисел – показания счетчиков через T
полных секунд для всех генераторов, приведенные последовательно от 1-го до N-го генератора.

например:
input.txt
2 1
1 2
10
output.txt
10 11