Ограничения: время – 1000ms/2000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Энди подарили игрушечную железную дорогу, и он сразу же построил большой игрушечный город.
Город состоит из делового центра и `N` жилых районов (пронумерованных от 1 до `N`), некоторые из которых связаны друг с другом
или с центром двусторонними железнодорожными линиями. Утром из каждого района отправляется поезд в центр по такому маршруту,
чтобы проезжать по дороге через минимально возможное количество промежуточных районов (т.е. с минимальным числом остановок).
Если есть несколько равноценных маршрутов, поезд может поехать по какому-нибудь одному из них (любому). Гарантируется, что от
любого района можно доехать до центра.
Для каждого района требуется найти минимальный и максимальный возможный объем транзита, т.е. количество (максимальное и минимальное) поездов,
проезжающих через него на своём пути к центру. Поезд, отправляющийся из района, не считается для этого района транзитным.
В первой строке вводятся два целых числа: `N` -- количество районов (`1 <= N <= 10^3`) и `M` -- количество
железнодорожных линий (`1 <= M <= N*(N-1)//2`). Затем следует `M` строк, каждая из которых описывает связывающую районы линию и
содержит пару целых чисел. Каждое число в паре — это номер района, либо 0 (если линия ведет в центр). Числа в паре различны.
Выведите `N` строк, по паре чисел в каждой: минимальное и максимальное количество поездов, проезжающих через
каждый из районов с номерами от 1 до `N` соответственно.
```sample Пример ввода
8 9
0 1
1 2
0 3
3 4
3 5
4 6
4 7
5 7
5 8
```
```sample Пример вывода
1 1
0 0
5 5
1 2
1 2
0 0
0 0
0 0
```
Пояснение: через район 1 обязательно проезжает поезд из района 2, и только он. Через район 3 обязательно проезжают поезда из районов с 4 по 8.
Через районы 4 и 5 обязательно проезжают поезда из районов 6 и 8 соответственно, а
также может (но не обязательно, т.к. кратчайших пути два) проезжать поезд из района 7.
Начало
Рабочее место участника
Поиск в ширину (BFS)