Hiking

Mirko and Slavko hike together. Mirko likes peaks and Slavko likes valleys. So every time they climb to a peak, Slavko picks the valley they descend to next, and every time they reach a valley, Mirko picks the peak they climb to next. They can only pick a spot that a trail leads to. No trail goes directly from one peak to another peak, and no trail goes directly from one valley to another valley. To keep the hike fun, they never visit the same spot twice, peak or valley. Once they reach a spot whose trails all lead to spots they have already visited, they call the mountain rangers and the hike ends there. If that last spot is a peak, Mirko wins. If it is a valley, Slavko wins.

Assume both of them play optimally. For every peak, determine who wins when the hike starts at that peak.

The first line contains two positive integers $N$ and $M$ ($1 \le N \le 5000$, $1 \le M \le \min(5000, N \times N)$). There are $N$ peaks and $N$ valleys, and $M$ is the number of trails.

Each of the next $M$ lines contains two positive integers $v_i$ and $d_i$ ($1 \le v_i, d_i \le N$), meaning that a trail connects peak $v_i$ and valley $d_i$.

At most one trail connects any given peak and valley.

Print $N$ lines. On line $i$, print the winner when the hike starts at peak $i$: print Mirko if Mirko wins, and Slavko if Slavko wins.

Here is how the second example works out.

Starting from peak 1, Slavko can choose valley 1, so Slavko wins.

Starting from peak 2, Slavko can choose valley 2, but then Mirko chooses peak 4 and wins.

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

Starting from peak 4, Slavko has to choose valley 2, and then Mirko chooses peak 2 and wins.