TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

Description

In bioinformatics analysis, Expressed Sequence Tags (ESTs) are small pieces of expressed DNA sequences that provide scientists with a quick method for annotating genes in the genome. The idea is to use huge amount of ESTs as tags to fish genes out of the genome by aligning ESTs to the genome. The DNA segments with EST-aligning evidence are then annotated as putative genes. The annotation of genes using ESTs is challenging due to the false-positive mapping in the alignment results (e.g., one EST mapping to multiple genes). Ideally, each EST should be mapped to only one gene. However, the alignment of ESTs to the genome often generate multiple matches for one EST (or multiple ESTs mapped to the same gene). Given the alignment results of ESTs to genes in the genome, now you are asked to develop a system for annotating maximum number of genes. Note that each EST can be only mapped to at most one gene and vice versa. The system should report the maximum number of annotating genes under this requirement.

  1. There are n ESTs and m genes, where 1 ≤ n, m ≤ 100.
  2. The ESTs are denoted as {E1, E2, ..., En
  3. The genes are denoted as {G1, G2, ..., Gm}. 
  4. For each EST Ei, its matched genes Gj are given, where 1 ≤ i, j ≤ 100.

Input Format

The input consists of a number of test cases. In each test case, the relationship between EST and its matched genes is given with the following format: The first line contains two positive integers 1 ≤ n, m ≤ 100, where n is the number of ESTs and m is number of genes. In the following n lines, each line represents one EST and contain indices of its matched genes separated by a single space. For example, if the second following line contains “1 3”, it represents that EST E2 is matched to genes G1 and G3. The next test case is separated from the previous one by one empty line.

Output Format

For each test case, output the maximum number of annotated genes in each line.

Sample Input 1

3 4 
1 2 3 
1 3 
4 

4 5 
1 5 
2 
3 4 
2 

Sample Output 1

3
3

Hints

Problem Source

Migrated from old NTUJ.

NCPC2007

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 200