Diagnosis

면접 대비

시간 제한1초메모리 제한2048 MB

요약
각 질병의 증상 집합과 진단된 질병 부분집합이 주어질 때, 그 증상들의 합집합이 환자의 전체 증상과 정확히 일치하는지 판정한다.
난이도

쉬움10점 중 3점

유형
해시맵, 배열, 구현, 완전 탐색
정답자
아직 제출이 없습니다

문제

In the PHP (Paradise Hospital of Prague) they cure people with a lot of different diseases. The PHP is dealing with a shortage of medical personal, therefore the director is afraid of doctors getting sloppy. Doctors make a diagnosis based on the knowledge they gained in university. So there is a known list of possible diseases and a known list of possible symptoms a patient can have. A doctor makes a diagnosis of one or multiple diseases. Those diseases have known symptoms that need to match exactly with the symptoms of the patient.

More formally: given a set of diseases D=d_1,d_2,...,d_nD = \\{d\_1, d\_2, ..., d\_n\\}, a set of symptoms S=s_1,s_2,...,s_mS = \\{s\_1, s\_2, ..., s\_m\\} and a function that represents the knowledge about diseases and their symptoms. f(d)=S′f(d) = S' with S′⊆SS' \subseteq S and d⊆Dd \subseteq D. When a given D′⊆DD' \subseteq D check whether or not the the condition S=⋃_d∈D′f(d)S = \bigcup\_{d \in D'}f(d) is true. When it is print "yes" else print "no".

입력

  • One line with two integers nn and mm, with 1≤n≤10001 \leq n \leq 1000 the number of diseases and 1≤m≤10001 \leq m \leq 1000 the number of symptoms. The patient has all symptoms s_1s\_1 to s_ms\_m.
  • One line with one integer kk followed by kk integers: the set of diseases D′D' the patient has according to the doctor (D′⊆D)(D' \subseteq D).
  • nn lines, corresponding to diseases d_1d\_1 to d_nd\_n, with an integer pp followed by pp integers: The symptoms belonging to disease ii. These symptoms are given in ascending order.

출력

Print "yes" if the symptoms of the diagnosed diseases exactly match the patient's symptoms. Print "no" otherwise.

예제2

  1. 예제 1

    입력
    5 6
    3 3 4 5
    3 1 2 3
    3 2 3 4
    2 5 6
    3 1 4 5
    4 1 2 3 5
    
    예상 출력
    yes
    
  2. 예제 2

    입력
    5 6
    4 1 2 4 5
    3 1 2 3
    3 2 3 4
    2 5 6
    3 1 4 5
    4 1 2 3 5
    
    예상 출력
    no