Задача №115451. Магическое заклинание
Великий маг планирует составить магическое заклинание. Заклинание состоит из рун, которые будем обозначать целыми числами. Заклинание, которое планирует составить маг, представляет собой перестановку \(p\), состоящую из \(n\) различных целых чисел от \(1\) до \(n\).
Для составления заклинания маг может использовать специальный волшебный справочник, содержащий \(m\) страниц, пронумерованных от \(1\) до \(m\), на каждой из которых записана одна руна, целое число от \(1\) до \(n\). К сожалению, маг уже стар и не может сам переписывать руны из справочника; к счастью, у него есть \(k\) учеников, которых он может в некотором порядке призвать к себе и попросить переписать фрагменты справочника на один общий длинный свиток. Если призвать \(i\)-го ученика, то он по порядку перепишет на свиток руны со страниц справочника от \(l_i\)-й до \(r_i\)-й, включительно. Учеников можно призывать в любом порядке, но каждого ученика можно призвать не более одного раза.
Например, пусть в справочнике \(m=6\) рун записаны в следующем порядке: \([2, 1, 3, 1, 2, 4]\), у мага \(k=3\) ученика с \(l_1=5\), \(r_1=6\); \(l_2=2\), \(r_2=6\) и \(l_3=1\), \(r_3=3\).
Если призвать сначала третьего, а затем первого ученика, они выпишут на свиток руны в следующем порядке: \([2, 1, 3, 2, 4]\).
А если призвать сначала второго, затем первого и затем третьего ученика, то на свитке получится последовательность рун \([1, 3, 1, 2, 4, 2, 4, 2, 1, 3]\).
После того, как на свиток будет переписано некоторое количество рун, маг может вырезать любой непрерывный отрезок свитка. Он хочет призвать минимальное количество учеников, чтобы в итоге он мог, вырезав непрерывный отрезок получившегося свитка, получить искомое магическое заклинание.
В примере выше, если заклинание представляет собой перестановку \([1, 3, 2, 4]\), то его можно получить, призвав сначала третьего, а затем первого ученика, и вырезав из получившегося свитка \([2, 1, 3, 2, 4]\) руны со 2-й по 5-ю.
Помогите магу определить, какое минимальное количество учеников он должен призвать и в каком порядке их нужно призывать, чтобы составить искомое заклинание, если это возможно.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число \(t\) (\(1 \le t \le 10^5\)) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит три целых числа \(n\), \(m\) и \(k\) (\(1 \le n \le 3 \cdot 10^5\), \(1 \le m \le 3 \cdot 10^5\), \(1 \le k \le 3 \cdot 10^5\)) — длина перестановки \(p\), количество страниц в книге и количество учеников.
Следующая строка содержит \(n\) различных целых чисел \(p_i\) (\(1 \le p_i \le n\)) — перестановку \(p\). Гарантируется, что все \(p_i\) попарно различны.
Следующая строка содержит \(m\) целых чисел \(a_i\) (\(1 \le a_i \le n\)) — руны, содержащиеся в книге.
Следующие \(k\) строк содержат по два целых числа, \(i\)-я из них содержит числа \(l_i\) и \(r_i\) (\(1 \le l_i \le r_i \le m\)), задающие отрезок страниц, которые переписывает \(i\)-й ученик.
Гарантируется, что суммы \(n\), \(m\) и \(k\) по всем наборам входных данных не превосходят \(3 \cdot 10^5\) соответственно.
Для каждого набора входных данных, если нельзя призвать учеников в некотором порядке так, чтобы перестановка \(p\) входила в выписанную на свиток последовательность рун как подотрезок, то выведите \(-1\).
Иначе выведите число \(c\) — минимальное количество призываемых учеников.
В следующей строке выведите \(c\) чисел — номера учеников в порядке, в котором их следует призывать. Ученики нумеруются целыми числами от \(1\) до \(k\) в порядке перечисления во входных данных. Все номера учеников должны быть попарно различными.
Если существует несколько оптимальных ответов, выведите любой из них.
2 4 6 3 1 3 2 4 2 1 3 1 2 4 5 6 2 6 1 3 3 4 1 3 1 2 2 1 3 1 1 4
2 3 1 -1