1810: Віяло
Перегляд у форматі PDFМаленька Оксі отримала у подарунок деревʼяну рамку у формі правильного багатокутника. Оскільки багатокутник має ~n~ вершин, він містить ~(n \times (n-3))/2~ деревʼяних паличок, які відповідають кожній можливій діагоналі. Вершини багатокутника позначені цілими числами від 1 до ~n~ проти годинникової стрілки. Спочатку Оксі розташувала ~n-3~ палички всередині рамки таким чином, що кожна паличка торкається двох несусідніх вершин рамки, і ніякі дві палички не перетинаються. Іншими словами, вона зробила тріангуляцію. Оскільки це було недостатньо цікаво для неї, вона вирішила пограти з цією конфігурацією, застосувавши певну операцію, яка складається з двох кроків:
- Зніміть паличку.
- Додаємо нову паличку таким чином, щоб отримати нову тріангуляцію.
Ми характеризуємо операцію впорядкованою парою невпорядкованих пар ~((a, b), (c, d))~, що означає, що маленька Оксі видалила паличку, яка торкається вершин ~a~ і ~b~, і додала паличку, що торкається вершин ~c~ і ~d~.
Оксі любить віяла, тому, виконуючи ці операції, вона іноді запитує себе: «Скільки операцій потрібно, щоб перетворити цю тріангуляцію на «віялову» тріангуляцію у вершині ~x~, і скількома способами це можливо зробити?».
Оскільки маленька Оксі зайнята операціями та розважається, то вона просить вашої допомоги!
«Віялова» тріангуляція у вершині ~x~ - це тріангуляція, де всі діагоналі мають спільну кінцеву точку, а саме вершину ~х~.
Нехай кількість необхідних операцій дорівнює ~m~. Нехай ~f_1, f2, . . . , f_m~ - це послідовність операцій, які при застосуванні в заданому порядку досягають бажаної тріангуляції, таким чином представляючи один із шляхів досягнення цього. Нехай ~s_1, s_2, . . . , s_m~ є іншою такою послідовністю. Дві послідовності є різними, якщо існує такий індекс ~i~, що ~f_i \neq s_i~.
Оскільки кількість таких послідовностей може бути дуже багато, то маленьку Оксі цікавить лише її залишок від ділення за модулем ~10^9 + 7~.
Формат вхідних даних
У першому рядку цілі числа ~n~ і ~q~ (~4 ≤ n ≤ 2·10^5~,~1 ≤ q ≤ 2·10^5~), кількість вершин і кількість подій
У кожному з наступних ~n - 3~ рядків записані цілі числа ~x_i, y_i~ (~1 ≤ x_i, y_i ≤ n~) — мітки вершин, яких торкається ~i~-та паличка.
У кожному з наступних ~q~ рядків є ціле число ~t_i~ (~1 ≤ t_i ≤ 2~), яке представляє тип події. Якщо ~t_i = 1~, за ним йдуть 4 цілі числа ~a_i, b_i, c_i, d_i~ (~1 ≤ a_i, b_i, c_i, d_i ≤ n~), які означають операцію ~((a_i, b_i), (c_i, d_i)~, яка виконується в цей момент. Гарантовано, що дана операція може бути реалізована. Якщо ~t_i = 2~, за ним йде ціле число ~x_i~ (~1 ≤ x_i ≤ n~), що означає, що маленьку Оксі цікавлять дані для «віялової» тріангуляції у вершині ~x_i~ по відношенню до поточної тріангуляції.
Формат вихідних даних
Для кожної події типу 2, у порядку їх надходження на вхід, виведіть два цілі числа: мінімальну кількість необхідних операцій і кількість способів дістатися до цільової тріангуляції за допомогою мінімальної кількості операцій.
Оцінювання
- тести 1-3 - 0 балів
- тести 4-13 (~n≤9,q≤1000~) - 10 балів
- тести 14-21 (~x_i =1,y_i =i+2~ для ~i=1,...,n-3~ і подій типу 1 немає - 15 балів
- тести 22-29 (~q=1~) - 25 балів
- тести 30-41 (~n,q ≤ 1000~) - 10 балів
- тести 42-55 (Жодних додаткових обмежень) - 40 балів
Пояснення
До першого прикладу: Початок тріангуляції вже є «віяльною» тріангуляцією у вершині 1, тому маленька Оксі не повинна виконувати жодних операцій, щоб можна зробити одним способом. Після виконання даної операції тепер є лише один спосіб повернути її до попереднього стану, а саме застосувати операцію ~((2, 4), (1, 3))~.
До другого прикладу: Єдина послідовність операцій для першого запиту: ~((3, 5), (1, 4))~.
Єдина послідовність операцій для другого запиту: ~((1, 3), (2, 5))~, ~((3, 5), (2, 4))~.
Єдина послідовність операцій для третього запиту: ~((3, 5), (2, 5))~.
Приклад вхідних даних
4 3
1 3
2 1
1 1 3 2 4
2 1
Приклад вихідних даних
0 1
1 1
Приклад вхідних даних
5 4
1 3
3 5
2 1
2 2
1 1 3 2 5
2 2
Приклад вихідних даних
1 1
2 1
1 1
Приклад вхідних даних
9 3
1 5
1 7
2 4
2 5
5 7
7 9
2 1
1 2 5 1 4
2 1
Приклад вихідних даних
4 12
3 6
Коментарі
5 балів нараховується за проходження тестів з умови
Чому коли потрібно переставити 2 палички відповідь 2 а не 1?
На запитання "чому" зараз не відповідають
ps Надалі треба ставити запитання більш конкретно - який приклад, яка фігура і т.п