Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 3909
Gene Cluster

Time Limit: 1 Second      Memory Limit: 65536 KB

Gene clusters are common features of plants. Most clustered genes known are involved in the biosynthesis of secondary metabolites.The indentification of gene cluster means a lot for scientific research.Lets do this interesting work.
A feature of gene cluster is coexpression.There are two type of genes,special and common.Every common gene in its cluster coexpresses with at least one other gene in the same cluster.In other words,if a common  gene coexpresses with another gene(no matter special or common) which is in a cluster,this common gene could be added into the cluster and the cluster will be bigger.You could also ignore this fact and the cluster retain its size(The fact is that in this case,you will try to add it so long as it is possible).However, special genes play an important role in biochemical reactions,so their indentification should be carefull.A special gene coexpress with at least two other genes(no matter special or common) in a cluster.A gene could be involved in more than one cluster.A cluster should contain at least 3 genes.

To clarify this problem,two tips following:
• Genes in a cluster are combined as one part by their coexpression relationships.
• If A coexpresses with B and B coexpresses with C, it doesn’t necessarily mean that A coexpresses with C.

The gene cluster which contains the biggest number of genes is called the biggest gene cluster.Given a set of genes with their type and coexpression information,please tell us how many genes are involved in the biggest gene cluster.

#### Input

There are multiple test cases. The first line of input is an integer T indicates the number of test cases. For each test case:
Each line contains 2 integers n and k (0<n <=100000,0<=k<10000) ― the number of coexpression gene pairs and the number of special genes,n lines following,listing the names of two coexpression genes, one pair per line,then k lines follow, listing the names of special genes,one name per line,those special genes are not neccesserily in the coexpression gene pairs above.Other genes not in the list are common.A gene name consists of a capital letter S and 4 digital number.

#### Output

For each case,print the number of genes in the biggest gene cluster.If the given genes can’t form any cluster,print “None”.

```2
4 2
S0001 S0002
S0002 S0003
S0003 S0004
S0007 S0009
S0002
S0004

2 1
S1001 S1003
S1002 S1003
S1001
```

```3
None
```

#### Hint

Case 1: The biggest cluster is S0001,S0002,S0003 and the answer is 3. S0002 is special and coexpresses with two genes(S0001 and S0003),so it can be added. S0004 is special but coexpresses with only one gene(S0003),so it can’t be added.

Case 2:Two genes can not form a cluster.

You could just image genes are cities and coexpression are roads,In the choosen group,all cities are combined by roads,special city has at least two direct ways to other two cities in group,common city has at least one direct way to another city in group,the question is that if a group has most cities(if the number is less than 3,it can't be called a group),print the number of cities in the group.

Author: ZHANG, Xingchen
Source: ZOJ Monthly, October 2015
Submit    Status