Canadian Computing Olympiad: 2016 Day 1, Problem 1
As a special treat for your kindergarten class, you're taking them on a field trip to a magical place of wonder.
Your class has
students, numbered from
to
for convenience. There are
direct, two-way friendships that exist between the students. Each student is friends with at most two other students.
Aside from the
direct friendships, students may also be acquainted with one another. Two students
and
are acquaintances if they're friends, or if there exists a third student
who is an acquaintance of both students
and
. For example, if
,
,
and
are pairs of students with a direct friendship, then person
and person
are acquaintances.
You're getting ready to order buses for the trip, but there are two issues. Firstly, the transportation company insists that every bus you order must be filled exactly to its capacity of
students. They won't allow you to order a bus if you intend to put fewer than
students on it! Secondly, the students are picky about their travelling conditions. Each student
will refuse to get on a bus unless both of the following conditions are met:
- All of the other students getting on that bus are acquaintances of student
;
- All of student
's acquaintances are getting on that bus.
Unfortunately, it looks like you might not be able to bring your whole class on this trip after all. However, you'll do whatever it takes to get as many students as possible on buses. As it turns out, "whatever it takes" may involve putting an end to a friendship or two, for the greater good. You may choose to sever
or more of the
friendships amongst the students, which will of course also have an effect on which students are acquainted with one another.
Determine the maximum number of students which can be brought on the trip, such that they're loaded onto buses with exactly
students each, and every student is satisfied with their bus allocation. Furthermore, since you're feeling generous, determine the minimum number of friendships which you can sever in order to be able to bring that many students along.
Input Specification
The first line contains three space-separated integers
,
and
;
;
.
The next
lines contain information about the friendships. That is, each of these
lines contain two space-separated integers
and
describing that students
and
are friends
. Note that no friendship is specified twice (that is, no two unordered friendship pairs are equal to one another).
For
of the
marks available,
.
Output Specification
The output consists of two space-separated integers printed on one line. The first integer is the maximum number of students which can be brought on the trip. The second integer is the minimum number of friendships which must be severed in order to bring that many students.
Sample Input
Copy
8 5 2
1 4
8 2
4 5
6 2
3 5
Sample Output
Copy
6 2
Explanation
If the friendships between student pairs
and
are severed, then
buses can be filled as follows:
- Bus
: Students
and 
- Bus
: Students
and 
- Bus
: Students
and 
Comments
There can be cycles right?