22051번 - Топологическая сортировка и дети 스페셜 저지다국어

Дан ациклический ориентированный граф с n вершинами, пронумерованными от 1 до n. Топологической сортировкой будем называть перестановку p чисел от 1 до n, что для любого ребра v → u выполняется p(v) < p(u).

Мальчику Саше дали задание найти топологическую сортировку ациклического графа. Как прилежный ученик он выполнил задание, записал ответ на доске и пошёл отдыхать. Когда Саша отошёл, пришёл непоседливый мальчик Сеня и стёр некоторые числа, оставив на их месте размазню.

Саша отдохнул и с ужасом увидел, что на доске не хватает чисел. Так как мела осталось мало, он хочет вписать только числа на месте стёртых, не меняя остальные, чтобы получить корректную топологическую сортировку. Помогите ему.

Первая строка содержит одно целое число t — число тестовых примеров. Далее следуют описания тестов. Каждый тест содержит описание графа и топологической сортировки. В первой строке теста содержится два числа n и m (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 10⁶) — число вершин и число рёбер. Следующие m строк содержат по два числа каждая — номер исходящей вершины и номер входящей вершины ребра. Последняя строка теста содержит перестановку чисел от 1 до n — топологическую сортировку заданного графа: для каждой вершины указан ее номер в топологической сортировке, число 0 означает, что соответствующее число было стёрто.

Сумма количеств вершин по всем тестам не превышает 10⁵. Сумма количеств ребёр по всем тестам не превышает 10⁶.

Для каждого тестового примера выведите на отдельной строке n натуральных чисел — корректную топологическую сортировку в описанном в условии формате. Гарантируется, что ответ существует.