Топологическая сортировка и дети
시간 제한5초메모리 제한256 MB
DAG와 일부 자리가 지워진 위상 정렬이 주어질 때, 지워진 자리에 수를 채워 전체가 올바른 위상 정렬이 되도록 복원한다.
문제
Дан ациклический ориентированный граф с n вершинами, пронумерованными от 1 до n. Топологической сортировкой будем называть перестановку p чисел от 1 до n, что для любого ребра v → u выполняется p(v) < p(u).
Мальчику Саше дали задание найти топологическую сортировку ациклического графа. Как прилежный ученик он выполнил задание, записал ответ на доске и пошёл отдыхать. Когда Саша отошёл, пришёл непоседливый мальчик Сеня и стёр некоторые числа, оставив на их месте размазню.
Саша отдохнул и с ужасом увидел, что на доске не хватает чисел. Так как мела осталось мало, он хочет вписать только числа на месте стёртых, не меняя остальные, чтобы получить корректную топологическую сортировку. Помогите ему.
입력
Первая строка содержит одно целое число t — число тестовых примеров. Далее следуют описания тестов. Каждый тест содержит описание графа и топологической сортировки. В первой строке теста содержится два числа n и m (1 ≤ n ≤ 105, 0 ≤ m ≤ 106) — число вершин и число рёбер. Следующие m строк содержат по два числа каждая — номер исходящей вершины и номер входящей вершины ребра. Последняя строка теста содержит перестановку чисел от 1 до n — топологическую сортировку заданного графа: для каждой вершины указан ее номер в топологической сортировке, число 0 означает, что соответствующее число было стёрто.
Сумма количеств вершин по всем тестам не превышает 105. Сумма количеств ребёр по всем тестам не превышает 106.
출력
Для каждого тестового примера выведите на отдельной строке n натуральных чисел — корректную топологическую сортировку в описанном в условии формате. Гарантируется, что ответ существует.