1 \(s / 256\) \(MB / 160\) points

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.

In test cases worth 30% of total points, it will hold 1 ≤ \(N\) ≤ 10 and 1 ≤ \(M\) ≤ \(N\) · \(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.

1 \(s / 256\) \(MB / 160\) points

The first line contains two positive integers, \(N\) and \(M\) (1 ≤ \(N \le 5000\), 1 ≤ \(M \le mi\)n(5000, \(N\) · \(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\) (1 ≤ \(v\) {i}{ }, \(d\) _{i} ≤ \(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.

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

생성자가 기록되지 않았습니다.

출처 COCI 2017/2018 Contest 5