이킹은 자신의 마을에서 명령 체계가 매우 복잡하다는 것을 알아차렸습니다. 마을에는 총 n명의 바이킹이 살고 있으며, 이들을 1번부터 n번까지 번호를 붙여 구분합니다. 이킹은 m개의 숫자 쌍 (a_i, b_i)를 적어두었는데, 이는 a_i번 바이킹이 b_i번 바이킹에게 명령을 내릴 수 있음을 나타냅니다. 명령을 받은 바이킹은 자신이 명령을 내릴 수 있는 다른 바이킹에게 이를 전달할 수도 있습니다.
x번 바이킹의 명령이 y번 바이킹에게 도달할 수 있다면, 우리는 y번 바이킹이 x번 바이킹의 지휘를 받는다고 말합니다.
이킹은 이 체계가 매우 복잡하고 비효율적이라고 생각하여 새로운 명령 체계를 도입하기로 했습니다. 새로운 체계는 다음 조건을 만족해야 합니다:
- 한 명의 리더가 있으며, 이 리더는 누구의 명령도 받지 않습니다.
- 리더를 제외한 각 바이킹은 정확히 한 명의 바이킹으로부터 명령을 받을 수 있습니다.
- 리더의 명령은 마을의 모든 바이킹에게 도달할 수 있어야 합니다.
즉, 새로운 명령 체계는 루트를 가진 트리 구조로 나타나며, 간선은 루트에서부터 나머지 노드로 방향이 지정됩니다. 또한, 새로운 체계에서의 각 바이킹 x의 지휘를 받는 바이킹의 집합은 기존 체계에서와 동일해야 합니다.
이킹은 적절한 체계를 아직 찾지 못했습니다. 이킹을 도와 이러한 체계가 존재하는지 확인하고, 존재한다면 해당 체계를 구해주세요.
입력
첫 번째 줄에는 두 개의 정수 n과 m이 주어집니다. 이는 각각 마을에 있는 바이킹의 수와 기존 체계에서 한 바이킹이 다른 바이킹에게 명령을 내릴 수 있는 관계의 수를 나타냅니다. (1<=n,m<=500,000)
다음 m개의 줄에는 정수 a_i, b_i가 주어지며, 이는 기존 체계에서 a_i번 바이킹이 b_i번 바이킹에게 명령을 내릴 수 있음을 나타냅니다. (1<=a_i,b_i<=n; a_i!=b_i)
같은 숫자 쌍이 여러 번 등장할 수 있습니다.
출력
만약 원하는 체계가 존재하지 않는다면 No를 출력합니다.
체계가 존재한다면 첫 번째 줄에 Yes를 출력하고, 두 번째 줄에 n개의 정수 p_1, p_2,...,p_n을 출력합니다.
여기서 i번 바이킹이 새로운 체계에서 리더라면 p_i=-1, 그렇지 않다면 p_i는 새로운 체계에서 i번 바이킹에게 명령을 내릴 수 있는 바이킹의 번호입니다. (1<=p_i<=n, i!=p_i)
yimjunhyuck 1년 전 1
문제
이킹은 자신의 마을에서 명령 체계가 매우 복잡하다는 것을 알아차렸습니다. 마을에는 총 n명의 바이킹이 살고 있으며, 이들을 1번부터 n번까지 번호를 붙여 구분합니다. 이킹은 m개의 숫자 쌍 (a_i, b_i)를 적어두었는데, 이는 a_i번 바이킹이 b_i번 바이킹에게 명령을 내릴 수 있음을 나타냅니다. 명령을 받은 바이킹은 자신이 명령을 내릴 수 있는 다른 바이킹에게 이를 전달할 수도 있습니다.
x번 바이킹의 명령이 y번 바이킹에게 도달할 수 있다면, 우리는 y번 바이킹이 x번 바이킹의 지휘를 받는다고 말합니다.
이킹은 이 체계가 매우 복잡하고 비효율적이라고 생각하여 새로운 명령 체계를 도입하기로 했습니다. 새로운 체계는 다음 조건을 만족해야 합니다:
- 한 명의 리더가 있으며, 이 리더는 누구의 명령도 받지 않습니다.
- 리더를 제외한 각 바이킹은 정확히 한 명의 바이킹으로부터 명령을 받을 수 있습니다.
- 리더의 명령은 마을의 모든 바이킹에게 도달할 수 있어야 합니다.
즉, 새로운 명령 체계는 루트를 가진 트리 구조로 나타나며, 간선은 루트에서부터 나머지 노드로 방향이 지정됩니다. 또한, 새로운 체계에서의 각 바이킹 x의 지휘를 받는 바이킹의 집합은 기존 체계에서와 동일해야 합니다.
이킹은 적절한 체계를 아직 찾지 못했습니다. 이킹을 도와 이러한 체계가 존재하는지 확인하고, 존재한다면 해당 체계를 구해주세요.
입력
첫 번째 줄에는 두 개의 정수 n과 m이 주어집니다. 이는 각각 마을에 있는 바이킹의 수와 기존 체계에서 한 바이킹이 다른 바이킹에게 명령을 내릴 수 있는 관계의 수를 나타냅니다. (1<=n,m<=500,000)
다음 m개의 줄에는 정수 a_i, b_i가 주어지며, 이는 기존 체계에서 a_i번 바이킹이 b_i번 바이킹에게 명령을 내릴 수 있음을 나타냅니다. (1<=a_i,b_i<=n; a_i!=b_i)
같은 숫자 쌍이 여러 번 등장할 수 있습니다.
출력
만약 원하는 체계가 존재하지 않는다면 No를 출력합니다.
체계가 존재한다면 첫 번째 줄에 Yes를 출력하고, 두 번째 줄에 n개의 정수 p_1, p_2,...,p_n을 출력합니다.
여기서 i번 바이킹이 새로운 체계에서 리더라면 p_i=-1, 그렇지 않다면 p_i는 새로운 체계에서 i번 바이킹에게 명령을 내릴 수 있는 바이킹의 번호입니다. (1<=p_i<=n, i!=p_i)