3-й этап Республиканской олимпиады по информатике 2022-2023, 2й тур

Задача E. Покраска графа

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

Дан ориентированный ацикличный граф из $N$ вершин и $M$ ребер. Вершины пронумерованы целыми числами от $1$ до $N$. Причем в графе нет ребра из вершины $1$ в вершину $N$. Все вершины изначального белого цвета. Мансуру нужно покрасить ровно $B$ вершин в черный цвет. После покраски удаляются все ребра у которых оба конца одного цвета. Помогите Мансуру покрасить $B$ вершин таким образом, чтобы нельзя было добраться из $1$ в $N$ после удаления всех ребер у которых оба конца одного цвета.

Формат входного файла

Каждый тест содержит несколько наборов входных данных. Первая строка содержит одно целое число $T$($1 <= T <= 100$) — количество входных данных. Первая строка каждого набора входных данных содержит три целых числа $N$,$M$ и $B$($3 <= N <= 10^5$, $0 <= M <= min(2 \cdot 10^5,\frac{N \cdot (N - 1)}{2})$, $1 <= B <= N$). Следующие $M$ строк каждого набора входных данных содержат по два целых числа $u$ и $v$($1 <= u, v <= N$, $u \ne v$, $(u,v) \ne (1, N)$) — задающие ориентированное ребро из вершины $u$ в вершину $v$. Гарантируется, что в графе нет цикл и повторяющихся ребер. Cумма $N$ по всем наборам входных данных не превосходит $10^6$. Cумма $M$ по всем наборам входных данных не превосходит $10^6$.

Формат выходного файла

Если невозможно покрасить нужным образом, выведите <<-1>>. Иначе, выведите $B$ различных целых числа — номера вершин которые нужно покрасить в черный цвет. Если есть несколько возможных ответов, выведите любую из них.

Пример:

Вход

2
15 16 5
1 2
1 3
1 4
1 5
2 7
3 7
4 8
5 7
7 9
8 9
9 10
9 11
9 12
10 15
11 15
12 15
3 2 2
2 3
1 2

Ответ

1 8 10 7 9
2 3

Замечание

( Temirlan Satylkhanov )