Choosing a Bias

Time limit2sMemory limit256 MB

Summary
Given N friends and M members, each friend lists acceptable members; decide if a distinct member can be assigned to each of the N friends.
Level

Medium7 of 10

Topics
Graph, String, Hash map, Brute force
Solved
No attempts yet

Problem

Heukseok and Sangdo like CAU (Complete & Awesome Unit), the best girl group in the country. In CAU there are several members that Heukseok likes and several members that Sangdo likes.

Heukseok and Sangdo want to pick their bias, the member they like most. However, because of the friendship between the two friends, they are not allowed to pick the same member as their bias.

So, to keep the friends' friendship, we want to assign each of them one bias member, all distinct.

Write a program that determines whether their friendship can be kept.

Input

The first line gives the number of friends NN and the number of girl group members MM. (2≤N,M≤10002 \le N, M \le 1000)

The next MM lines each give the name of a girl group member. A member's name consists only of uppercase English letters and is at most 100 characters long.

The next NN lines each give, for one friend, the number of members they like KK (1≤K≤M1 \le K \le M) followed by the names of the girl group members they like, separated by spaces.

Output

The first line reports whether the friends' friendship can be kept. Print YES if it can, and NO if it cannot.

If the friendship cannot be kept, the second line prints the maximum number of members the friends as a whole can like without any overlap.

Examples2

  1. Example 1

    Input
    4 5
YEJI
LIA
RYUJIN
CHAERYEONG
YUNA
3 YEJI RYUJIN YUNA
2 LIA RYUJIN
3 CHAERYEONG YEJI RYUJIN
4 LIA RYUJIN CHAERYEONG YUNA
    Expected output
    YES

  2. Example 2

    Input
    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
    Expected output
    NO
5