D. Ханын будаг

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Хэрэглэгч Айнта хана будахаар шийдсэн. Хана нь $n × n$ хүснэгтээр зохион байгуулагдсан ба $n^{2}$ хавтангуудаас бүрдсэн байна. Зарим хавтан будагдсан, бусад нь будагдаагүй. Тэр сайхан будахыг хүссэн учраас доорх дүрмүүдийг дагах болно.

  1. Эхлээд хэрэглэгч Айнтa ханыг харна. Хэрвээ мөр бүрээс дор хаяж нэг нүд будагдсан ба багана тус бүрээс дор хаяж нэг нүд будагдсан байгаа бол тэр будалтаа зогсооно. Үгүй бол тэр алхам 2 руу шилжинэ.
  2. Хэрэглэгч Айнта ижил магадлалтайгаар ханын аль нэг хавтанг сонгоно.
  3. Хэрвээ сонгосон хавтан будагдаагүй бол тэр хавтанг будна. Эсрэг тохиолдолд тоохгүй орхино.
  4. Хэрвээ тэр хавтанг будаагүй бол дараа нь нэг минут амрана. Үүний дараа алхам 1 рүү шилжинэ.   Энэ ажлыг дуусгахын тулд хэтэрхий их цаг зарцуулах тул Айнта санаа зовж байна. Тэгэхээр тэр дээрх аргаар ханыг будахад шаардлагатай цагыг тооцолохыг хүсэж байна. Хүлээгдэж буй цагыг олоход нь түүнд тусал. Та аль ч хавтанг сонгох болон будахад ямар ч цаг зарцуулдагүй гэж үзэж болно.

Оролт

Эхний мөр нь $n$, $m$ ($1 ≤ n ≤ 2*10^{3}$; $0 ≤ m ≤ min(n^{2}, 2*10^{4})$) бүхэл тоонуудыг агуулна. Эдгээр нь ханын хэмжээ болон будагдсан нүднүүдийн тоо юм.

Дараа нь $m$ мөрүүд байх бөгөд мөр бүр бөгөөд мөр бүр $r_{i}$, $c_{i}$ ($1 ≤ r_{i}, c_{i} ≤ n$) хоёр бүхэл тоо агуулна. Энэ бол будагдсан нүдний байрлал. Эдгээр байрлалууд бүгд ялгаатай байна. Хүснэгтийн мөрүүд $1$-с $n$ хүртэл, баганууд $1$-с $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
Сэтгэгдлүүдийг ачааллаж байна...