На площині задано n точок, пронумерованих від 1 до n. Вони утворюють орієнтовний цикл 1 → 2 → ... → n → 1. Вам потрібно виконати наступну операцію декілька разів: за номерам двох точок a та b потрібно вирізати частину цикла від точки a до точки b і вставити цей шматок назад, але у зворотному порядку, так що вирізаний шматок вставляється у порядку від b до a. Знайдіть довжину кінцевого циклу.
Перший рядок містить два числа n та m (3 ≤ n, m ≤ 100000). Наступні n рядків містять два числа x[i]
та y[i]
- координати i-ої точки. Наступні m рядків містять два числа a[i]
та b[i]
- номери точок i-ї операції.
Вивести довжину фінального циклу з двома десятковими знаками.
Початковий цикл: 1 → 2 → 3 → 4 → 5 → 1
Після першої операції: 1 → 5 → 3 → 4 → 2 → 1(частина 5 → 1 → 2 заміняється на 2 → 1 → 5)
Після другої операції: 1 → 2 → 4 → 3 → 5 → 1 (частина 5 → 3 → 4 → 2 заміняється на 2 → 4 → 3 → 5)
Після третьої операції: 1 → 2 → 5 → 3 → 4 → 1