CJAT01 - Compete or Not

Peter and John, want to team up in a school's competition. However, preparation for the contest wastes a lot of time. So, they only want to join, if they can guarantee that they can win.

Since the registration for the competition is not yet open, they can't know anything about the teams they are facing. So they decided to go through the whole school, and see if any 2 can make up a team that beat theirs. However, the number of students might be very great, so they want you to write a program that helps them identifying whether they should register or not.

Usually students take this competition seriously, that they study very hard, that if a student is good in a given course, he won't fail a question regarding this course. Therefore, a team is expected to win, if the number of unique courses the team members take is greater than the number of unique courses taken by the members of the opposing team.

Also the competition regulations require, that same team members must share at least N courses.

Your task is to say whether Peter and John can win the competition if they participate or not.

Input

Input has multiple test cases terminated by "-1".

Each test contains an integer N, representing the minimum number of shared courses required to join the competition, then consecutive lists of courses taken by each student, and will be terminated by "#".

A course will be represented by an uppercase or a lowercase character, the list of courses for a given student will end by the character "0". Note that "a" and "A" don't represent the same course, and there will be 0 or more whitespace and/or newline characters between courses.

The first 2 students in each test case represent Peter and John.

Be careful, Large Input/Output for some test cases.

Output

For every test case, print "YES" or "NO", on a single line, on whether Peter and John will win the competition or not.

Example

Input:
1
ABC0
AEF0
#
2
AB C D   E F
a bc de f0
Aa ZYX WVQ
RST0
AEG0
AGf0
#
1
A0
A0
ABCDF0
abcdf0
#
1
A0
A0
ABCDF0
Abcdf0
#
-1

Output:
YES
YES
YES
NO

Added by:Mahmoud Aladdin
Date:2013-04-05
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ASM32-GCC MAWK BC C-CLANG C NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Own Creation

hide comments
2021-05-22 16:26:37
Clarifications:
- there can be up to 60 students per testcase, including John and Peter,
- answer is "YES" only if John and Peter can beat every possible team of 2 students.

Very hard to make TL in PyPy the way I solved this, but there exists a certain algorithm that some better coders might try applying here.

I'd lean towards moving this to Classical.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.