Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

MWP4_2E - Newsy

W tym roku główną nagrodą na MWWSIP jest dwutygodniowy wyjazd na Wyspy Kanaryjskie!!! - taką treść miała wiadomość SMS, którą Janek wysłał do Piotrka o godzinie 9:30. Niestety zmuszeni jesteśmy zdementować tą wiadomość - jak powszechnie wiadomo panuje kryzys i mimo, że jeszcze nie wiemy co będzie główną nagrodą na pewno nie będą to wczasy na Wyspach Kanaryjskich. Problem w tym, że Piotrek przesłał wiadomość dalej - do Maćka i Jarka, a Ci również chcieli przekazać innym tą radosną nowinę i w taki właśnie sposób plotka obiegła naszą uczelnię. Z nieoficjalnych źródeł udało nam się dowiedzieć kto jest sprawcą zamieszania teraz musimy jeszcze poinformować o całej sytuacji wszystkich wprowadzonych w błąd. Dotarliśmy do bilingów naszych studentów i na ich podstawie zamierzamy odtworzyć łańcuch po jakim rozchodziła się nieprawdziwa wiadomość. Znamy sprawcę zamieszania, mamy bilingi, wiemy też że każdy kto otrzymał wiadomość o nagrodzie pisał już wyłącznie o niej - pomóż nam i napisz program który ustali przebieg zdarzeń. Kolejność podanych na wejściu wiadomości jest chronologiczna.

Wejście

W pierwszej linii wejścia znajduje się dokładnie jedna liczba całkowita Z (1 ≤ Z ≤ 10) określająca liczbę zestawów danych.

W pierwszej linii każdego zestawu znajdują się 3 liczby i, j, k (1 ≤ i, k ≤ 25000; 1 ≤ j ≤ 50000) oznaczające odpowiednio: liczbę osób które wysyłały do siebie wiadomości, liczbę wiadomości jakie zostały wysłane i numer osoby o której wiemy, że jest źródłem plotek. W kolejnych j liniach znajdują się opisy wysyłanych wiadomości. Zapis 1 2 oznacza że osoba z numerem 1 wysłała wiadomość tekstową do osoby numer 2.

Wyjście

Na wyjściu należy w oddzielnej linii dla każdego zestawu danych wypisać łańcuszek osób, które kolejno dowiadywały się o nieprawdziwej historii.

Przykład

Wejście:

1
6 8 5
1 3
3 5
4 6
5 2
3 4
2 6
3 6
2 4

Wyjście:

5 2 6 4

Dodane przez:Maciej Boniecki
Data dodania:2012-03-18
Limit czasu wykonania programu:0.100s-0.662s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:IV Mistrzostwa WWSI w Programowaniu
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.