변이 먼저인가, 정점이 먼저인가

2020년, 세계는 대그래프 시대다. 세계는 "그래프는 변에서 먼저 태어났다"고 주장하는 변파와 "그래프는 정점에서 먼저 태어났다"고 주장하는 정점파로 크게 갈라져 혼란에 빠졌다. 주장을 맞세우는 양파가 도달한 싸움의 궁극형이 그래프를 사용한 2인 게임이다. 오늘도 변파의 에지오 씨와 정점파의 버텍스코 씨가 이 게임으로 겨룰 예정이다.

이 게임에서는 먼저 N개의 정점과 M개의 변으로 이루어진 유향 그래프가 주어진다. 게임은 선수 페이즈, 후수 페이즈, 평가 페이즈의 세 단계로 순서대로 진행된다.

1. 선수 페이즈: 선수는 변파의 에지오 씨이며, 이 페이즈에서 M개의 변 중 정확히 1개의 변을 무작위로 고르기 위한 확률을 에지오 씨가 정한다. 즉 모든 변에 대해 i번째 변이 선택될 확률 ei를 마음대로 배정한다. 여기서 각 ei는 0 이상 1 이하인 실수이고, 모든 ei의 합은 정확히 1이어야 한다.
2. 후수 페이즈: 후수인 정점파의 버텍스코 씨는 N개의 정점 중 정확히 1개의 정점을 무작위로 고르기 위한 확률을 정한다. 즉 모든 정점에 대해 j번째 정점이 선택될 확률 vj를 마음대로 배정한다. 변과 마찬가지로 각 vj는 0 이상 1 이하인 실수이고, 모든 vj의 합은 정확히 1이어야 한다. 후수는 선수가 변에 배정한 확률을 자유롭게 본 뒤에 확률을 배정할 수 있다.
3. 평가 페이즈: 배정된 확률에 따라 변 1개와 정점 1개를 독립적으로 무작위로 정한다. 선택된 변과 정점의 관계에 따라 게임의 점수를 다음과 같이 정한다.

• 정점이 유향변의 시점이면 점수는 -1이다.
• 정점이 유향변의 종점이면 점수는 1이다.
• 정점이 유향변의 시점도 종점도 아니면 점수는 0이다.

이 게임에서 후수인 정점파의 버텍스코 씨는 점수의 기댓값을 최소화하도록 확률을 배정한다. 물론 정점이 변보다 먼저 와야 한다고 생각하기 때문이다. 한편 선수인 변파의 에지오 씨는 후수인 버텍스코 씨가 점수의 기댓값을 최소화하는 전략을 취한다는 점을 고려한 뒤, 점수의 기댓값을 최대화하도록 확률을 배정한다. 말할 것도 없이 변이 정점보다 먼저 와야 한다고 생각하기 때문이다. 주어진 그래프에서 두 사람이 위 전략에 따라 변과 정점에 확률을 배정할 때, 점수의 기댓값을 구하시오.

입력은 50개 이하의 데이터 세트로 이루어진다. 각 데이터 세트는 다음 형식으로 주어진다.

N M
a1 b1
…
aM bM

1행은 게임에 사용하는 유향 그래프의 정점 수 N (2 ≤ N ≤ 104)과 변 수 M (1 ≤ M ≤ 104)으로 이루어진다. 이어지는 M행은 그래프의 유향변 정보를 나타낸다. M행 중 i행은 i번째 변의 시점이 ai (1 ≤ ai ≤ N)번째 정점이고, 종점이 bi (1 ≤ bi ≤ N)번째 정점임을 나타낸다. 주어지는 그래프에는 자기 루프가 없다. 즉 모든 1 ≤ i ≤ M에 대해 ai ≠ bi를 만족한다. 주어지는 그래프에는 중복 변이 없다. 즉 모든 1 ≤ i < j ≤ M에 대해 ai ≠ aj 또는 bi ≠ bj 중 하나를 만족한다.

입력의 끝은 두 개의 0으로 이루어진 행으로 나타낸다.

주어진 그래프에서 두 사람이 위의 각각의 최적 전략을 취할 때의 게임 점수의 기댓값을 1행에 출력하시오. 결과는 10−10 이상의 오차를 포함해서는 안 된다.