TLE '16 Contest 8 P5 - Prom Night

View as PDF
Submit solution
Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M
Author:
ZQFMGB12
Problem type
A good prom-alternate activity (don't be a normie!).

Every male competitive programmer knows that finding a prom date is both more competitive and more difficult than any programming competition. It's almost time for prom, but the CS nerd still doesn't have a prom date! Of course, he really wants to take the girl out. Unfortunately, he knows this won't happen, so he won't go to the event. Despite this, he is still interested in his options for prom.

There are N males and M females in the school. Each male is willing to go to prom with a non-negative number of females. Every student is given an identification number. Males are numbered from 1 to N and females are separately numbered from 1 to M. The CS nerd's ID number is 1 (and he is a male).

Other males will always get to choose a single female for their prom date before the CS nerd does. Once a female is chosen, another male cannot choose her. Males will always try to choose one female they are willing to go to prom with, but this is not always possible. The CS nerd then wonders to himself: "What is the minimum number of females I can choose from?" Can you help him out?

Constraints

In all subtasks:

1 \le N,M

Subtask Points N,M
1 20 N,M \le 5
2 30 N,M \le 10
3 50 N,M \le 100

Input Specification

The first line of input will contain two integers, N and M.

N lines of input follow. The first integer will be t_i (0 \le t_i \le M). t_i space-separated integers follow, specifying the ID numbers of the females the i^\text{th} male is willing to go to prom with. All of the ID numbers on each line will be distinct.

Output Specification

Output the minimum number of females that the CS nerd can choose from.

Sample Input 1

2 2
1 1
2 1 2

Sample Output 1

0

Explanation for Sample Output 1

If male 2 chooses female 1, the CS nerd cannot choose any female.

Sample Input 2

3 3
3 1 2 3
3 1 2 3
3 1 2 3

Sample Output 2

1

Sample Input 3

3 4
2 1 2
1 2
2 2 4

Sample Output 3

1

Comments


  • -2
    Plasmatic  commented on Aug. 11, 2018, 7:56 p.m.

    Sample input

    5 10
10 1 2 3 4 5 6 7 8 9 10
1 1
1 1
1 1
1 1

    = cs nerd has no standards


  • 0
    Evan_Yu123  commented on Sept. 8, 2017, 1:41 p.m.

    This question is pure cringe...


    • 7
      account_disabled  commented on March 6, 2018, 2:12 p.m.

      I came to code! Not to be painfully reminded of my problems!


    • 0
      kobortor  commented on Sept. 8, 2017, 4:27 p.m.

      No u


  • -8
    GirishRengadurai  commented on May 5, 2017, 6:23 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 15
      imaxblue  commented on May 30, 2017, 10:53 p.m.

      50% of girls at CCO used pascal


      • 7
        Kirito  commented on May 31, 2017, 1:46 a.m.

        Didn't the guy who beat d also use Pascal?


  • 28
    MongolianPoorman  commented on April 22, 2017, 9:00 p.m.

    CS nerd = Jim Gao


    • 22
      jimgao  commented on April 22, 2017, 10:38 p.m.

      Life is hard sometimes.


  • 26
    Cthulhu  commented on April 21, 2017, 3:56 a.m.

    The CS nerd then wonders to himself: "What is the minimum number of females I can choose from?"

    I'm shocked that he can't get a date.


    • 25
      imaxblue  commented on April 21, 2017, 1:45 p.m.

      He needs to learn to go with the flow


      • -1
        Pavlo87  commented on May 31, 2017, 12:10 a.m.

        He should consider learning the Ford–Fulkerson algorithm.