시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 403 | 164 | 122 | 40.940% |
곰곰이는 좋아하는 음료수 자판기가 있다. 이 자판기에는 "랜덤" 버튼이 있는데, 이 버튼을 누르면 이세계에서 출발한 음료수가 $M$ 번의 차원 이동 후 자판기 상품 출구로 떨어진다.
하지만 차원 이동은 불안정하기 때문에, 음료수 종류가 도중에 바뀌는 일도 있다. 정확히는 아래와 같은 규칙에 의해 바뀐다.
곰곰이는 $1$ 부터 $N$ 까지 모든 종류의 음료수에 대해, 각각 $M$ 번의 차원 이동을 거쳐 최종적으로 어떤 종류의 음료수가 되는지 알고 싶다.
첫 번째 줄에 음료수의 종류 개수 $N$, 차원 이동 횟수 $M$ 이 공백을 사이에 두고 주어진다. $(2 \le N, M \le 300\,000)$
두 번째 줄부터 $M$개의 줄에 걸쳐 정수 $U_i, V_i$ 가 공백을 사이에 두고 주어진다. $(1 \le i \le M,\ 1 \le U_i, V_i \le N,\ U_i \ne V_i)$
$f(k)$ 가 음료수 종류 $k$ 가 $M$ 번의 차원 이동을 거쳐 최종적으로 변하는 음료수 종류라고 할 때, $f(1), f(2), \cdots, f(N)$ 을 첫 번째 줄에 공백을 사이에 두고 출력하라.
5 4 1 3 3 2 4 3 2 4
4 4 4 3 5