valeralandsber

17.06.2020 18:35

Информатика

Есть ответ 👍

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

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

робота добраться до красной стены. робот в данном лабиринте ведет себя следующим образом: каждый раз он случайно (равновероятно) выбирает дверь, ведущую в сторону от центра. в каких помещениях робот будет заканчивать работу чаще? определите вероятности попадания робота в помещения с красной стеной.

формат входных данных

в первой строке программе подается целое число n (1≤n≤102) — количество дверей.

далее в n строках через пробел записываются пары целых чисел a, b (0≤a, b≤n,a≠b) — номера помещений, которые соединены дверью.

формат выходных данных

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

номера помещений запишите в порядке возрастания;
после каждого номера поставьте двоеточие;
затем через пробел укажите вероятность попадания в указанное помещение. если вероятность является целым числом, укажите это число. если вероятность — дробное число, то запишите его в виде простой дроби x/y, где нод(x,y)=1.
система оценки

за будут начислены, если все тесты будут пройдены успешно.

sample input:

23
0 1
0 2
0 3
0 9
1 16
1 17
16 15
15 14
15 13
17 21
17 18
18 19
18 20
2 4
2 5
4 6
4 7
5 8
3 22
9 23
9 10
10 11
10 12
sample output:

6: 1/16
7: 1/16
8: 1/8
11: 1/16
12: 1/16
13: 1/16
14: 1/16
19: 1/32
20: 1/32
21: 1/16
22: 1/4
23: 1/8