GOSSIPER - Gossipers

no tags 

Doulnee Keltchow is a small town in the middle of nowhere; what makes it so famous is the number of gossipers who live there. Every morning, each gossiper finds out a new gossip, a gossip so unique that nobody else in the town knows it. The gossipers talk, gossip and exchange rumors all day long. What happens when two gossipers meet? Of course, they exchange all the gossips they have heard so far. Your task is to determine whether every gossiper will know all the gossips by the end of the day.

Input file specification

The input file consists of multiple test cases separated by blank lines. On the first line of every test case there are two positive integers N (1<=N<=2100) and M (1<=M<=12000), where N is the number of gossipers and M is the number of meetings. On the next N lines there are the names of the gossipers. The name of each gossiper is a single word consisting of lower- and uppercase letters. The following M lines describe the meetings in the order they happened. Each meeting is described by two distinct names of the gossipers separated by a single space. The values M=N=0 indicate the end of the input file.

Output file specification

The output file should contain for each test case one line containing a single word "YES" if every gossiper knows all the gossips, or "NO", otherwise.

Example

Input file:
3 3
Alice
Bob
Cindy
Alice Bob
Bob Cindy
Cindy Alice

4 4
Kirk
Lucy
Mike
Nancy
Kirk Lucy
Lucy Mike
Mike Nancy
Nancy Lucy

0 0

Output file:
YES
NO

hide comments
vengatesh15: 2017-02-01 13:36:09

tried different and AC in 1 go:-)

Ayur Jain: 2015-01-01 20:44:21

Time limit is very linent!

anurag garg: 2013-12-25 09:38:43

can two names start from the same character...??

Tarun Gehlaut: 2013-04-14 15:14:53

#Rajkiran
Consider it like this.
A shares his gossip with B.
So both know 2 distict gossips each. Now B and C meet so B has one more gossip in his tally so his count is 3 and all the gossips previously heard by B are also now known by C. So C also has heard 3 gossips. A still has 1. So A has to either meet with B or C. Hope it answers your question

Rajkiran Rajkumar: 2012-03-08 00:03:22

If A and B have met, and B and C have met, then A and C need not meet, am I right? Please clarify.

Iqram Mahmud: 2010-08-16 06:36:18

I think less than 100.

Stephen Oberholtzer: 2010-01-03 19:58:35

What is the maximum length of a gossiper's name?


Added by:Fudan University Problem Setters
Date:2007-12-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO
Resource:IPSC 2001