## CCO '16 P1 - Field Trip

View as PDF

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

Author:
Problem type

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

8 5 2
1 4
8 2
4 5
6 2
3 5

#### Sample Output

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