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

Есеп E. Графты бояу

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

1 second

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

256 megabytes

$N$ төбеден және $M$ бағытталған қырдан тұратын тұзақсыз граф беріледі. Төбелер $1$ден $N$ге дейн сандармен нөмірленген. Графта $1$ мен $N$ төбесін қосатын қыр жоқ. Басында барлық төбе ақ түспен боялған. Мансұрға дәл $B$ төбені қара түске бояу қажет. Боялған соң, екі шетінің түсі бірдей болатын қырлар жойылып кетеді. Екі шетінің түсі бірдей қырлар жойылған соң, $1$-ден $N$-ге жол болмайтындай Мансұрға боялатын $B$ нүктеңі таңдауға көмектесіңіз .

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

Әр тестте бірнеше кіріс жиынтығы бар. Бірінші жолда бір бүтін сан $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$ға бағытталған қыр. Графта қайталанатын қырлар жоқ және граф тұзақсыз. Тұзақсыз деген бір төбеден бастап, бірнеше қыр арқылы өтіп өзіне қайтып келуге болмайды дегенді білдіреді. Әр тесттегі $N$-дердің қосындысы $10^6$дан аспайды. Әр тесттегі $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 )