| Codeforces Round 115 |
|---|
| Закончено |
Вася играет в популярную игру Gnomes of Might and Magic.
В этой игре Вася управляет королевством гномов, состоящим из нескольких замков, соединенных двусторонними дорогами. Сеть дорог королевства имеет специальный вид. В королевстве есть m главных замков: a1, a2, ... , am, которые образуют Путь Добра. Этот путь состоит из дорог между замками ai, ai + 1 (1 ≤ i < m), а так же дороги между am и a1. Никаких других дорог между замками Пути Добра нет.
Кроме того, для каждой пары соседних замков Пути Добра u и v существует ровно один Обход Зла — путь по дорогам королевства, ведущий из первого замка (u) во второй (v) и не имеющий с Путем Добра общих вершин, кроме вершин u и v. Известно, что никаких других дорог и замков в королевстве нет, то есть каждая дорога и каждый замок лежит либо на Пути Добра, либо на Обходе Зла (замки могут лежать и там, и там). Кроме того, никакие два Обхода Зла не имеют общих замков, отличных от замков Пути Добра.
В начале каждой недели в королевстве появляется один очень плохой гном, который встает на одну из дорог королевства и начинает грабить корованы, проходящие через эту дорогу. На одной дороге может скапливаться несколько очень плохих гномов. Вася бережет свои корованы, поэтому иногда отправляет Миссию Смерти из одного замка в другой.
Пусть Миссия Смерти должна попасть из замка s в замок t. Тогда она будет двигаться из замка s к замку t, уничтожая всех очень плохих гномов, находящихся на дорогах пути, по которому она следует. Вася настолько крут, что его Миссия Смерти может уничтожить любое число гномов на своем пути. Однако, Вася очень добрый, поэтому всегда выбирает такой путь между замками s и t, следуя которому придется уничтожить наименьшее число гномов. Если таких путей несколько то среди них Вася выбирает путь, содержащий наименьшее число дорог. Если и таких путей несколько, то среди них Вася выбирает лексикографически минимальный.
Помогите Васе, промоделируйте жизнь королевства в игре Gnomes of Might and Magic.
Под путем понимается последовательность замков такая, что каждая пара соседних замков пути соединена дорогой. При этом путь x1, x2, ... , xp лексикографически меньше пути y1, y2, ... , yq, если либо p < q и x1 = y1, x2 = y2, ... , xp = yp, либо существует такое число r (r < p, r < q), что x1 = y1, x2 = y2, ... , xr = yr и xr + 1 < yr + 1.
В первой строке находятся два целых числа n и m (3 ≤ m ≤ n ≤ 100000) — количество замков в королевстве и количество замков на Пути Добра, соответственно.
Во второй строке находится m целых чисел — номера замков Пути Добра (замки нумеруются от 1 до n) в порядке следования по Пути, начиная с некоторого замка. Все замки Пути Добра различны.
Каждая из следующих m строк описывает один Обход Зла. Сначала в строке записано целое число ki (3 ≤ ki ≤ 100000) — количество замков на соответствующем Обходе Зла (с учетом двух замков, находящихся на пути добра), затем следует ki целых чисел — номера замков в порядке следования по данному Обходу. Все замки в одном Обходе Зла различны. Гарантируется, что первый и последний замки Обхода находятся на Пути Добра, а первые замки в Обходах Зла образуют Путь Добра и представлены в том же порядке, что и Путь во второй строке.
В следующей строке находится целое число q (1 ≤ q ≤ 100000) — количество событий в жизни королевства. Каждая из следующих q строк описывает одно событие. Событие описывается символом cj и двумя номерами замков sj и tj (символ и номера замков разделены единичным пробелом). Если символ cj равен «+» (плюс), то это означает, что на дороге между замками sj и tj встал (возможно, не первый) очень плохой гном. Если cj равен «?» (вопрос), то Вася направил Миссию Смерти из замка sj в замок tj. Гарантируется, что при запросе «+» дорога между замками sj и tj существует. События даны в хронологическом порядке, начиная с самого раннего. Изначально очень плохих гномов на дорогах нет.
Все числа во всех строках разделены единичными пробелами. Гарантируется, что все заданные Обходы Зла и Путь Добра соответствуют ограничениям, описанным в условии задачи.
Для каждого запроса «?» необходимо вывести единственное число на отдельной строчке — количество очень плохих гномов, уничтоженных соответствующей Миссией Смерти. Ответы на запросы нужно выводить в хронологическом порядке.
6 3
1 2 3
3 1 4 2
3 2 5 3
3 3 6 1
10
+ 1 2
+ 4 2
+ 1 3
+ 2 3
? 1 2
+ 2 5
? 1 2
? 1 2
+ 1 2
? 1 2
0
1
0
1
В примере после первых 4 запросов существует только один путь из замка 1 в замок 2, не содержащий дорог с очень плохими гномами: 1 
6 3 5 2.
После того, как гном встал на дорогу (2, 5), следующая Миссия Смерти движется по пути 1 2 и уничтожает гнома, находившегося на дороге (1, 2). Следующая Миссия смерти идет по этому же пути, уже свободному от гномов.
После того, как еще один гном встал на дорогу (1, 2), следующая Миссия Смерти идет по пути 1 2 и уничтожает этого гнома.
