Pokémon 토너먼트

Pokémon 챔피언 Simone는 친구들을 모아 토너먼트를 열었다. Pokémon 경기는 정확히 두 명의 선수 사이에서 치러지며 절대로 무승부로 끝나지 않는다. 또한 Pokémon 경기의 승자는 상대가 가진 돈의 정확히 절반을 받는다는 사실이 널리 알려져 있다. 처음에는 모두가 각각 $100$크로나를 가지고 있으며, 총 $M$번의 경기가 치러진다.

Simone는 모든 친구를 염탐했기 때문에 친구들의 실력을 정확히 알고 있다. 그녀는 모든 선수를 하나의 긴 목록에 순위대로 나열했으며, 두 사람이 맞붙으면 목록에서 더 위에 있는 사람이 항상 이긴다는 것을 알고 있다. 모든 선수에게는 목록에서의 위치에 따라 번호가 매겨져 있다. 당연히 가장 뛰어난 선수인 Simone의 번호는 따라서 $1$이다.

그녀는 치러질 경기의 목록을 이미 공개했지만, 경기 순서는 아직 정해지지 않았다. 이제 그녀는 경기 순서를 직접 정할 수 있을 때 마지막에 가질 수 있는 돈의 최댓값이 얼마인지 궁금하다. 이를 계산하는 프로그램을 작성하라!

채점

제출한 풀이는 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

1 | 20 | $N, M \le 8$

2 | 40 | $N, M \le 1\,000$, 각 선수는 최대 한 경기에서 패배한다

3 | 40 | $1 \le N \le 100\,000$, $0 \le M \le 200\,000$

첫째 줄에는 Simone를 포함한 선수의 수 $N$과 치러질 경기의 수 $M$을 나타내는 두 정수가 주어진다.

이어서 Simone의 목록에 있는 경기를 나타내는 $M$개의 줄이 주어진다. 각 경기는 맞붙을 두 선수의 번호인 두 정수 $1 \le a < b \le N$이 한 줄에 주어진다.

어떤 두 선수도 두 번 이상 맞붙지 않는다.

Simone가 경기 순서를 최적으로 정했을 때 대회가 끝난 후 가질 수 있는 크로나의 수를 소수로 출력한다. 답은 소수점 이하 적어도 $6$자리의 정밀도로 나타내야 한다.

Simone는 어떤 경기도 치르지 않으므로, 마지막에도 처음에 가지고 있던 100크로나만 갖게 된다.

가능한 순서 중 하나는 3번 경기를 치른 다음 2번 경기를 치르고, 마지막으로 1번 경기를 치르는 것이다.

첫 번째 경기가 끝난 후 선수들이 가진 돈은 (150, 100, 50)이다.

두 번째 경기가 끝난 후 선수들이 가진 돈은 (150, 125, 25)이다.

세 번째 경기가 끝난 후 선수들이 가진 돈은 (212.5, 62.5, 25)이다.