C. Плейлист
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Джефф смотрел в небо. Облаков почти не было, и летящие низко самолеты были отлично видны. Они выполняли замысловатые фигуры, то летели рядом, то уходили друг от друга в разные стороны. Джефф вспомнил, что где-то читал о репетиции к празднику. Праздник, конечно, хорошее дело, но вот репетиция так близко от жилых кварталов... Джефф достал наушники и, нащупав в кармане телефон, включил плеер. Зазвучала знакомая мелодия...

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

Плеер может воспроизводить композиции в двух режимах: в порядке плейлиста и в произвольном порядке. Джефф не помнит, как был настроен плеер, когда он слушал его в последний раз. Ваша задача — определить вероятность, что, прослушав k композиций, Джефф поймет, что плеер воспроизводит их в произвольном порядке.

Замечание. В любом из режимов плеер работает «по циклу».

Входные данные

В первой строке содержатся целые числа n и m (2 ≤ n ≤ 20,  1 ≤ m ≤ n) — количество музыкальных композиций в плейлисте и количество пар, для которых Джефф точно помнит порядок.

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

Гарантируется, что входные данные непротиворечивы.

Выходные данные

Выведите n - 1 строку.

В строке #j (j = 1, 2, ..., n - 1) выведите вероятность того, что Джефф после прослушивания композиции #j поймет, что плеер воспроизводит их в произвольном порядке.

Вероятности выводите с абсолютной или относительной погрешностью 10 - 6.

Примеры
Входные данные
4 2
PureParadise SunsetSamba
brio rubia
Выходные данные
0.000000000000
0.666666666667
0.166666666667
Примечание

Поясним приведенный пример.

Всего у нас 4 композиции, которые могут образовывать плейлист 4! = 24 способами. Вероятностью события будем называть отношение количества благоприятствующих ему исходов к общему количеству исходов. Ради краткости будем обозначать композиции буквами P, S, B, R.

Прослушав одну композицию (любую), Джефф не сможет сделать каких-либо выводов, поэтому соответствующая вероятность равна нулю.

Прослушав две композиции, Джефф сможет сделать вывод, что плейлист проигрывается в произвольном порядке, в следующих случаях:

  • первой прозвучала композиция P, а за ней — не S (т.е. либо B, либо R). Таких вариантов у нас 4: PBRS, PBSR, PRBS, PRSB;
  • первой прозвучала композиция B, а за ней — не R. Таких вариантов тоже 4 (аналогично предыдущему);
  • первой прозвучала композиция S, а за ней — P. Таких вариантов имеется 2: SPBR и SPRB;
  • первой прозвучала композиция S, а за ней — R (R должна следовать за B). Таких вариантов тоже два: SRPB и SRBP;.
  • первой прозвучала композиция R, а за ней — B. Таких вариантов 2;
  • первой прозвучала композиция R, а за ней — S. И таких вариантов тоже 2.

Таким образом, благоприятствующих исходов у нас будет 16, а вероятность составит 16 / 24 = 2 / 3.

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

  • прозвучали композиции P и S, после чего прозвучала композиция R (PSBR);
  • прозвучали композиции S и B, после чего прозвучала композиция P (SBPR);
  • прозвучали композиции B и R, после чего прозвучала композиция S (BRSP);
  • прозвучали композиции R и P, после чего прозвучала композиция B (RPBS);

Получается всего 4 благоприятствующих исхода, а вероятность составит 4 / 24 = 1 / 6.