축생도

시간 제한1초메모리 제한1024 MB

요약
1부터 N까지 값으로 이루어진 수열 A에서 A[i]와 A[A[i]]를 바꾸는 연산을 반복해 B로 만들 수 있는지 판정한다.
난이도

어려움10점 중 8점

유형
그래프, DFS, 수학, 조합론
정답자
아직 제출이 없습니다

문제

축생도의 호반우들은 NN 이하의 양의 정수로 이루어진 수열 A_1,A_2,⋯ ,A_NA\_{1}, A\_{2}, \cdots , A\_{N}에 다음 연산을 원하는 만큼 적용해 B_1,B_2,⋯ ,B_NB\_{1}, B\_{2}, \cdots , B\_{N}으로 만들어야 한다.

  • 임의의 ii를 골라 A_iA\_{i}와 A_A_iA\_{A\_{i}}의 값을 바꾼다.

호반우를 도와 축생도에서 깨달음을 얻어보자.

입력

첫째 줄에 NN이 주어진다. (1≤N≤300,000)(1 \leq N \leq 300\\,000)

둘째 줄에 수열 A_1,A_2,⋯ ,A_NA\_{1}, A\_{2}, \cdots , A\_{N}이 공백을 두고 주어진다. (1≤A_i≤N)(1 \leq A\_{i} \leq N)

셋째 줄에 수열 B_1,B_2,⋯ ,B_NB\_{1}, B\_{2}, \cdots , B\_{N}이 공백을 두고 주어진다. (1≤B_i≤N)(1 \leq B\_{i} \leq N)

출력

첫째 줄에 수열 AA를 BB로 만들 수 있다면 YES를, 그렇지 않다면 NO를 출력한다.

예제2

  1. 예제 1

    입력
    7
    5 4 1 3 2 3 6
    5 2 3 4 1 6 3
    
    예상 출력
    YES
    
  2. 예제 2

    입력
    7
    1 2 3 4 5 6 7
    2 2 3 3 4 5 6
    
    예상 출력
    NO