B. Красим стену
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Пользователь ainta решил разрисовать стену. Стена состоит из n2 плиток, расположенных в виде таблицы размера n × n. Некоторые плитки окрашены, другие — нет. Юноша хочет покрасить стену красиво и поэтому будет красить ее по следующим правилам:

  1. Сначала пользователь ainta внимательно смотрит на стену. Если в каждой строке стены есть хотя бы одна окрашенная плитка, и в каждом столбце стены есть хотя бы одна окрашенная плитка, он прекращает покраску. В противном случае, он переходит к пункту 2.
  2. Пользователь ainta равновероятно выбирает любую плитку стены.
  3. Если выбранная плитка не окрашена, она красится. В противном случае она игнорируется.
  4. Затем ainta отдыхает одну минуту, даже если он не покрасил плитку в предыдущем пункте. После чего он переходит снова к пункту 1.
 

Все же ainta беспокоится, не слишком ли долго придется красить стену описанным алгоритмом. Поэтому он хочет подсчитать математическое ожидание затраченного времени при использовании описанного выше алгоритма покраски. Помогите ему. Можете считать, что на выбор и окраску плитки время не тратится.

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

В первой строке записано два целых числа, n и m (1 ≤ n ≤ 2·103; 0 ≤ m ≤ min(n2, 2·104)) — размер стены и количество изначально окрашенных ячеек.

Затем следует m строк, в каждой записано по два целых числа, ri и ci (1 ≤ ri, ci ≤ n) — номер строки и номер столбца очередной окрашенной плитки на стене. Гарантируется, что все позиции окрашенных плиток различны.

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

В единственной строке выведите математическое ожидание времени, необходимого на покраску стены, в минутах. Ваш ответ будет считаться правильным, если величина его абсолютной или относительной погрешности не превышает 10 - 4.

Примеры
Входные данные
5 2
2 3
4 1
Выходные данные
11.7669491886
Входные данные
2 2
1 1
1 2
Выходные данные
2.0000000000
Входные данные
1 1
1 1
Выходные данные
0.0000000000