COCI '17 Contest 5 #6 Planinarenje

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

Mirko and Slavko like to hike together. Mirko likes mountain peaks, and Slavko likes valleys. Because of this, every time they climb to a peak, Slavko decides which valley they are going to descend to, given that a trail exists to it. Similarly, in each valley, Mirko decides which peak they are going to climb up to. It will never be possible to directly climb from one peak to another, or to get from one valley to another valley. In order to make the hiking as fun as possible, they never visit the same spot twice (whether it's a peak or a valley). Once they reach a spot that only leads to spots they've visited before, they call the mountain rangers to pick them up. If the final spot is a peak, Mirko wins, and if it is a valley, Slavko wins.

Naturally, you must already know what your task is: If we assume that both of them play optimally, who wins? Answer this question for all initial peaks.

Input Specification

The first line contains two positive integers, N and M (1 \leq N \leq 5\,000, 1 \leq M \leq \min(5\,000, N \times N)).

Here, N denotes the number of peaks and valleys (therefore, there are N peaks and N valleys), and M denotes the number of hiking trails.

Each of the following M lines contains two positive integers: v_i and d_i (1 \leq v_i, d_i \leq N) that denote there is a trail between peak v_i and valley d_i.

Between each peak and valley, there will exist at most one trail.

Output Specification

You must output N lines. The i^\text{th} line denotes the winner if the starting point is peak i.

Scoring

In test cases worth 30\% of total points, it will hold 1 \leq N \leq 10 and 1 \leq M \leq N \times N.

In test cases worth an additional 20\% of total points, for each two connected spots, there will exist a unique path between them. In other words, the graph will be a forest.

Sample Input 1

2 3
1 2
2 2
2 1

Sample Output 1

Slavko
Slavko

Sample Input 2

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

Sample Output 2

Slavko
Mirko
Mirko
Mirko

Explanation for Sample Output 2

Starting from the first peak, Slavko can choose to go to the first valley, so Slavko wins.

Starting from the second peak, Slavko can choose to go to the second valley, after which Mirko wins by choosing to go to the fourth peak.

Starting from the third peak, there are no trails, so Mirko wins.

Starting from the fourth peak, Slavko must choose to go to the second valley, after which Mirko wins by choosing the second peak.

Sample Input 3

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

Sample Output 3

Slavko
Slavko
Mirko
Slavko

Comments

There are no comments at the moment.