최애 정하기

시간 제한2초메모리 제한256 MB

요약
N명의 친구와 M명의 멤버가 주어지고 각 친구가 좋아하는 멤버 목록이 있을 때, 모든 친구에게 서로 다른 멤버를 배정할 수 있는지 판별한다.
난이도

보통10점 중 7점

유형
그래프, 문자열, 해시맵, 완전 탐색
정답자
아직 제출이 없습니다

문제

흑석이와 상도는 국내 최고의 걸그룹인 CAU(Complete & Awesome Unit)를 좋아한다. CAU에는 흑석이와 상도가 좋아하는 멤버가 각각 여러 명 존재한다.

흑석이와 상도는 가장 좋아하는 멤버인 최애 멤버를 정하려고 한다. 그런데 두 친구가 같은 멤버를 최애로 삼는 것은 두 친구 사이의 우정 때문에 허락되지 않는다.

따라서 친구들의 우정을 지키기 위해, 최애 멤버 1명씩을 서로 다른 멤버로 정하려고 한다.

친구들의 우정을 지킬 수 있는지 판별하는 프로그램을 작성해 보자.

입력

첫째 줄에 친구의 수 NN과 걸그룹의 멤버 수 MM이 주어진다. (2≤N,M≤10002 \le N, M \le 1000)

다음 MM개 줄에 걸쳐 걸그룹 멤버의 이름이 각각 주어진다. 걸그룹 멤버의 이름은 영문 대문자로만 이뤄져 있으며, 최대 길이는 100글자이다.

다음 NN개 줄에 걸쳐 친구마다 좋아하는 멤버 수 KK(1≤K≤M1 \le K \le M)와 좋아하는 걸그룹 멤버 이름들이 공백을 사이에 두고 주어진다.

출력

첫 번째 줄에는 친구들의 우정을 지킬 수 있는지 여부를 출력한다. 지킬 수 있으면 YES, 지킬 수 없으면 NO를 출력한다.

우정을 지킬 수 없는 경우 두 번째 줄에는 친구들 전체가 서로 겹치지 않게 좋아할 수 있는 최대 멤버 수를 출력한다.

예제2

  1. 예제 1

    입력
    4 5
    YEJI
    LIA
    RYUJIN
    CHAERYEONG
    YUNA
    3 YEJI RYUJIN YUNA
    2 LIA RYUJIN
    3 CHAERYEONG YEJI RYUJIN
    4 LIA RYUJIN CHAERYEONG YUNA
    
    예상 출력
    YES
    
  2. 예제 2

    입력
    6 6
    MIYEON
    MINNIE
    SOOJIN
    SOYEON
    YUQI
    SHUHUA
    2 YUQI SOOJIN
    1 SOYEON
    1 YUQI
    2 YUQI SHUHUA
    3 MIYEON SOYEON YUQI
    3 MIYEON SHUHUA SOYEON
    
    예상 출력
    NO
    5