루미 알고리즘

#1287플래티넘Gruppindelning

PO 2008 온라인 예선코딩스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

Under en skolutflykt ska eleverna delas in i olika grupper. Naturligtvis vill eleverna vara i samma grupp som sina kompisar. Skriv ett program som, givet namnet på varje elev samt vem som är kompis med vem, beräknar det maximala antalet grupper som eleverna kan delas in i (om eleverna får som de vill).

Indata

På första raden står ett heltal: antalet elever som ska på utflykt (2 ≤ n ≤ 100). Därefter följer n rader, var och en innehållande namnet på en elev. Varje namn är mellan 1 och 20 tecken långt och innehåller endast bokstäverna A-Z. Alla elever har olika namn.

Sedan följer en rad med ett heltal: antalet kompispar (1 ≤ m ≤ 4950). Slutligen följer m rader innehållande kompisparen. För varje par anges två namn på samma rad, separerade med ett mellanslag.

Utdata

Programmet ska skriva ut en rad med ett heltal: det maximala antalet grupper som eleverna kan delas in i.

예제

예제 1

입력
6
KALLE
MAJA
SARA
SVEN
HUGO
ANNA
3
KALLE ANNA
MAJA ANNA
SARA HUGO
출력
3

출처 표기

출처: Programmeringsolympiaden 2008년 온라인 예선 · 원문 페이지 · 이용 조건 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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.