eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Цикл точок

Цикл точок

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

На площині задано n точок, пронумерованих від 1 до n. Вони утворюють орієнтовний цикл 12 → ... → n1. Вам потрібно виконати наступну операцію декілька разів: за номерам двох точок a та b потрібно вирізати частину цикла від точки a до точки b і вставити цей шматок назад, але у зворотному порядку, так що вирізаний шматок вставляється у порядку від b до a. Знайдіть довжину кінцевого циклу.

Вхідні дані

Перший рядок містить два числа n та m (3n, m100000). Наступні n рядків містять два числа x[i] та y[i] - координати i-ої точки. Наступні m рядків містять два числа a[i] та b[i] - номери точок i-ї операції.

Вихідні дані

Вивести довжину фінального циклу з двома десятковими знаками.

Приклад

Вхідні дані #1
5 3
0 0
1 0
2 0
2 2
0 2
5 2
5 2
4 5
Вихідні дані #1
10.89

Примітка

  1. Початковий цикл: 123451

  2. Після першої операції: 153421(частина 512 заміняється на 215)

  3. Після другої операції: 124351 (частина 5342 заміняється на 2435)

  4. Після третьої операції: 125341

Автор Олексій Щепін
Джерело ACM-ICPC Ukraine 2013, 2nd Stage Ukraine, September 10-12, 2013