루미 알고리즘

#1271플래티넘Kulturkrockar

PO 2004 결선코딩출제 Jimmy Mårdell, Håkan Strömberg, Pär Söderhjelm스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Historiker är ofta intresserade av i vilken kultur och vid vilken tidpunkt en viss uppfinning först uppstod. Detta är dock inte så lätt att veta eftersom olika kulturer då och då mötts och utbytt information. Om man vet vilka sådana utbyten som har ägt rum och vilka kulturer som känner till uppfinningen idag, kan man ibland räkna ut var den har uppstått. Du ska skriva ett program som gör just detta.

Vi ska använda en mycket förenklad modell av kulturers möten. Vi tänker oss n kulturer (numrerade från 1 till n) som lever helt isolerade utom vid vissa tidpunkter då det sker ett fullständigt utbyte av information mellan två kulturer. Vi behöver inte bry oss om huruvida det rör sig om fredligt samarbete eller krigserövringar, det enda viktiga är att om uppfinningen var känd i den ena kulturen före mötet, så är den känd i båda kulturerna efter mötet. Notera att antalet kulturer aldrig ändras. Efter mötet fortsätter de två kulturerna att vara isolerade och kan samverka på olika sätt med andra kulturer. Det enda vi vet säkert, är att omedelbart efter mötet bär dessa två kulturer på exakt samma kunskap.

Indata

På första raden i indatan står två heltal n och k, där 2 ≤ n ≤ 1000 och 1 ≤ k ≤ 10000. n är antalet kulturer i vår modell och k är det totala antalet möten vi betraktar. Därefter kommer k rader med vardera två heltal a och b, båda i intervallet 1...n. Varje rad beskriver ett möte mellan kultur nummer a och kultur nummer b. Mötena inträffar i precis den ordning som anges. Varje möte antas vara fullkomligt avslutat innan nästa möte äger rum.

Efter mötesbeskrivningarna följer en rad med ett heltal 2 ≤ m ≤ n, antalet kulturer som idag känner till uppfinningen, och på följande rad m heltal i intervallet 1...n, som anger numren på de kulturer som idag känner till uppfinningen.

Utdata

Programmet ska skriva en lista med heltal i intervallet 1...n. Varje tal anger numret på en kultur i vilken uppfinningen kan ha uppstått. Eller mer precist uttryckt: Om det för varje kultur x finns en möjlig tidpunkt för uppfinningen som gör att spridningen av uppfinningen idag är exakt så som anges, då ska x finnas med i listan, annars inte. Alla talen i listan ska vara olika och sorterade i stigande ordning.

예제

예제 1

입력
6 7
5 6
5 4
2 4
3 5
6 2
1 3
4 5
4
1 3 4 5
출력
3 5 

출처 표기

출처: Programmeringsolympiaden 2004년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.