Baltic Olympiad in Informatics: 2018 Day 1, Problem 1
As we all know, TV soap operas with many characters can lead to seriously complicated love dramas. In one TV show, there are ~N~ characters. Each character loves exactly one character (which could actually be him- or herself). We say that two characters are in a relationship if and only if they love each other.
One particular type of complication is called a "love polygon". We say that 3 or more characters are in a "love polygon" if the first character loves the second, the second loves the third and so on, and also the last character loves the first.
Recent polling has shown that viewers have grown tired of this drama and would prefer something more romantic. Therefore, it was decided to shoot some characters with love arrows so that everyone is in a relationship. By shooting someone with a love arrow, you can change whom that character loves (to any character of your choice).
What is the least number of love arrows needed to get everyone into a relationship?
The first line of the input contains the integer ~N~, the number of characters involved. The next ~N~ lines all contain two space-separated names ~s~ and ~t~, meaning that the character named ~s~ initially loves the character named ~t~. Names of the characters are no more than 10 letters long and consist of lowercase English letters.
Output one integer – the minimum number of love arrows needed to get everyone into a relationship. If this is not possible, output -1.
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.
|1||21||~2 \le N \le 20~||None.|
|2||25||~2 \le N \le 10^5~||Each character is loved by someone, possibly themselves.|
|3||29||~2 \le N \le 10^5~||Initially, there are no relationships or love polygons.|
|4||25||~2 \le N \le 10^5~||None.|
Explanation of Samples
The first example is illustrated in the figure above. The upper part shows the initial love situation, where an arrow pointing from ~s~ to ~t~ indicates that ~s~ initially loves ~t~, and the pink color highlights the three characters that needs to be shot with love arrows in the unique optimal solution. The lower part shows the situation afterwards.
In the second example (which satisfies the constraints of group 3), there are several optimal solutions. One of them is to shoot
d with love arrows, and have them fall in love with
In the third example, we have a love triangle, where no matter how many love arrows we shoot, someone will always be left out.
Sample Input 1
8 leonard emmy ada emmy isaac leonard emmy pierre pierre bernhard bernhard emmy sofia karl karl sofia
Sample Output 1
Sample Input 2
4 a c b c c d d d
Sample Output 2
Sample Input 3
3 rocky scarlet scarlet patrick patrick rocky
Sample Output 3