## Baltic OI '17 P1 - Political Development

View as PDF

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 1G

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
##### Baltic Olympiad in Informatics: 2017 Day 1, Problem 1

A certain political party with members wants to develop some brand new politics. In order to do so, the party plans to make a committee for new political development. Clearly, the best politics is developed when all committee members disagree with each other, and when the committee is as large as possible.

In order to figure out which pairs of politicians disagree and which don't, the party then arranged for every possible pair of politicians to discuss a randomly selected topic. Whenever two politicians couldn't agree on their assigned topic, this was recorded in the party's Book of Great Achievements.

Armed with this book, you have now been assigned the task of finding the largest committee where everyone disagrees. However, finding a large committee can prove challenging; careful analysis have revealed that for any non-empty group of party members, there is always at least one member of the group who disagrees with (strictly) less than of the other group members. Obviously, then, the committee can not have more than members. But is there a choice of committee of this size? Find the size of a largest possible committe such that nobody in that committee agrees.

#### Input Specification

The first line contains two integers, the number of members in the party, and as described above. Each member is indicated by an integer between and . After the first line follow lines, one for each politician , starting with . The line for politician begins with an integer , and is followed by integers indicating with which other party members the th politician disagrees according to the Book of Great Achievements.

#### Constraints

We always have , and . For subcases, the inputs have these further restrictions:

• Group 1: 4 points
• Group 2: 12 points
• Group 3: 23 points Each party member disagrees with at most other members.
• Group 4: 38 points
• Group 5: 23 points

#### Output Specification

Output a single integer, the size of the largest possible committee.

#### Sample Input 1

5 3
2 1 2
3 0 2 3
3 0 1 4
2 1 4
2 2 3

#### Sample Output 1

3

#### Sample Input 2

5 3
3 1 2 4
1 0
1 0
0
1 0

#### Sample Output 2

2