(DeepL로 영어로 번역한 텍스트를 중역했습니다. 오역이 있으면 답글로 달아주세요. 감사합니다 🙇)
문제
훈련이 제일 좋아~ 대원들 모여라♪
오늘도 박한별 장군은 n명의 부대원을 집합시켜 1번부터 n번까지의 번호를 붙였다. 부대원들은 1오 횡대로 집합한 상태이며, i번째 자리에는 ai번 부대원이 서 있다. 집합이 완료되면 은하 부관이 부대원들이 정해진 자리에 집합했는지 확인한다.
훈련이 한참 진행되는 도중 박한별 장군은 부대원들을 처음에 집합했던 순서대로 다시 집합시키려고 했지만, 부대원들의 정확한 자리 배치를 잊어버렸다! 다행히 은하 부관은 기억력이 좋기 때문에, m개의 순서쌍 (xi, yi)에 대해 xi번째 자리의 부대원 번호가 yi번째 자리의 부대원보다 작다는 것을 기억하고 있다.
은하 부관은 박한별 장군에게 기억한 순서쌍을 하나씩 보고하기 시작했다. 박한별 장군은 부대원들을 최대한 빨리 집합시키고 싶어하기 때문에, 지금까지 보고받은 순서쌍만으로 부대원들의 자리 배치를 유일하게 결정할 수 있을 때 즉시 집합 명령을 내릴 것이다. 은하 부관이 몇 개의 순서쌍을 보고해야 하는지 계산하는 프로그램을 작성하여라.
입력
첫째 줄에 훈련에 참여한 부대원의 수 n과 은하 부관이 기억한 순서쌍의 개수 m이 주어진다. (2 ≤ n ≤ 105, 1 ≤ m ≤ 105)
둘째 줄부터 m개의 줄에 걸쳐 은하 부관이 기억한 순서쌍 xi와 yi가 순서대로 주어진다. 이는 xi번째 자리의 부대원 번호가 yi번째 자리의 부대원보다 작다는 의미이다. (1 ≤ xi, yi ≤ n, xi ≠ yi)
같은 순서쌍이 여러 번 주어지지 않으며, 은하 부관의 기억은 항상 정확하기 때문에 주어지는 모든 순서쌍을 만족하는 자리 배치가 반드시 존재한다.
출력
은하 부관이 보고해야 하는 순서쌍 개수의 최솟값을 한 줄로 출력한다. 은하 부관이 모든 순서쌍을 보고해도 자리 배치가 유일하게 결정되지 않을 경우에는 -1을 대신 출력한다.
힌트
예제 입력 1의 경우, 올바른 자리 배치는 (5, 2, 1, 3, 4)이다. 박한별 장군은 4번째 순서쌍을 보고받는 즉시 이 자리 배치를 유일하게 결정할 수 있다.
예제 입력 2의 경우, 은하 부관의 기억과 일치하는 자리 배치는 (1, 3, 4, 2), (2, 3, 4, 1), (3, 2, 4, 1), (4, 2, 3, 1)의 4가지이다.
dlaud5379 1년 전 1
(DeepL로 영어로 번역한 텍스트를 중역했습니다. 오역이 있으면 답글로 달아주세요. 감사합니다 🙇)
문제
오늘도 박한별 장군은 n명의 부대원을 집합시켜 1번부터 n번까지의 번호를 붙였다. 부대원들은 1오 횡대로 집합한 상태이며, i번째 자리에는 ai번 부대원이 서 있다. 집합이 완료되면 은하 부관이 부대원들이 정해진 자리에 집합했는지 확인한다.
훈련이 한참 진행되는 도중 박한별 장군은 부대원들을 처음에 집합했던 순서대로 다시 집합시키려고 했지만, 부대원들의 정확한 자리 배치를 잊어버렸다! 다행히 은하 부관은 기억력이 좋기 때문에, m개의 순서쌍 (xi, yi)에 대해 xi번째 자리의 부대원 번호가 yi번째 자리의 부대원보다 작다는 것을 기억하고 있다.
은하 부관은 박한별 장군에게 기억한 순서쌍을 하나씩 보고하기 시작했다. 박한별 장군은 부대원들을 최대한 빨리 집합시키고 싶어하기 때문에, 지금까지 보고받은 순서쌍만으로 부대원들의 자리 배치를 유일하게 결정할 수 있을 때 즉시 집합 명령을 내릴 것이다. 은하 부관이 몇 개의 순서쌍을 보고해야 하는지 계산하는 프로그램을 작성하여라.
입력
첫째 줄에 훈련에 참여한 부대원의 수 n과 은하 부관이 기억한 순서쌍의 개수 m이 주어진다. (2 ≤ n ≤ 105, 1 ≤ m ≤ 105)
둘째 줄부터 m개의 줄에 걸쳐 은하 부관이 기억한 순서쌍 xi와 yi가 순서대로 주어진다. 이는 xi번째 자리의 부대원 번호가 yi번째 자리의 부대원보다 작다는 의미이다. (1 ≤ xi, yi ≤ n, xi ≠ yi)
같은 순서쌍이 여러 번 주어지지 않으며, 은하 부관의 기억은 항상 정확하기 때문에 주어지는 모든 순서쌍을 만족하는 자리 배치가 반드시 존재한다.
출력
은하 부관이 보고해야 하는 순서쌍 개수의 최솟값을 한 줄로 출력한다. 은하 부관이 모든 순서쌍을 보고해도 자리 배치가 유일하게 결정되지 않을 경우에는 -1을 대신 출력한다.
힌트
예제 입력 1의 경우, 올바른 자리 배치는 (5, 2, 1, 3, 4)이다. 박한별 장군은 4번째 순서쌍을 보고받는 즉시 이 자리 배치를 유일하게 결정할 수 있다.
예제 입력 2의 경우, 은하 부관의 기억과 일치하는 자리 배치는 (1, 3, 4, 2), (2, 3, 4, 1), (3, 2, 4, 1), (4, 2, 3, 1)의 4가지이다.