GROUPSProblem code: INS0902 |
In an Unix like environment, an administrator wants do following task: There n programs and k users. Each user has permission to execute certain programs. Now, the administrator wants to divide programs into minimum number of groups, so that each program belongs to an unique group, and assign users to these groups, such that only users belonging to the group have permissions to execute programs in the group.
Input
First line gives t, the number of test cases (t ≤ 30). Then t test cases follow.
For each test case:
The first line gives 2 integers n and k. (1 ≤ n ≤ 105 and 1≤ k ≤1000 )
Next k lines follow. Each line contains a set of integers. If an
integer "i" exists in a line "k" then the kth user has permission to execute program "i".
Output
For each test case output a single line.
Each line should give the minimum number of
groups possible.
Example
Input: 1 5 5 1 2 4 1 2 4 1 2 4 2 3 5 3 5 Output: 3
| Author: | fctrl |
| Date Added: | 14-10-2009 |
| Time Limit: | 9 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
The time limits for all the
The time limits for all the problems will be updated shortly.
The time limit for this
The time limit for this problem is 9 s
How do we know the number of
How do we know the number of intergers in the i'th line?
Are we expected to parse the input?
@chetan badam : scan the
@chetan badam : scan the entire line
what is the range of values
what is the range of values for i?
@SANTOSH K.S the programs are
@SANTOSH K.S the programs are sequentially numbered from 1.
Can you please laborate line
Can you please laborate line "and assign users to these groups, such that only users belonging to the group have permissions to execute programs in the group."?
Does it mean that if a group has prog 1,2 and users 1,2. then no users in any other group has access to any of prog 1,2?
If its possible, can you write the solution ofr sample test case. I mean how the progs and users are divided.
@Satyendra Mishra: yes.
@Satyendra Mishra: yes.