Однажды на одной из своих многочисленных поездок Петя и его друг Вася решили сходить в замок-музей. Музей был особой формы: он состоял из n комнат, соединенных m коридорами, так что из любой комнаты можно дойти до любой другой.

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

Но даже несмотря на всю спешку, они не могли насмотреться на произведения искусства, поэтому каждый из них действовал следующим образом: каждую минуту он решал куда ему идти — с вероятностью p_i он в эту минуту не совершал перехода (оставался в комнате), а с вероятностью 1 - p_i равновероятно выбирал одну из прилегающих комнат и переходит в нее по коридору. Здесь i — порядковый номер комнаты, в которой сейчас находится данный человек. В древности строительные работы стоили дорого, поэтому каждый коридор соединял две различные комнаты, при этом между любыми двумя комнатами было не более одного коридора.

Все действия ребята выполняли одновременно. В силу того, что в коридорах темно, в них встреча невозможна, однако по ним можно ходить в обоих направлениях (в том числе, и одновременно обоим ребятам, при этом встреча не происходит). Друзья действуют описанным образом, пока не встретятся. Более формально, встреча — это когда в какой-то момент времени они оба захотели оказаться в одной и той же комнате.

Для каждой из комнат найдите вероятность встречи в ней, при условии что в 6 часов вечера они находятся в комнатах a и b соответственно.