두근 어질

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

요약
꽃집마다 꽃이 한 송이씩 있는 님 게임을 N일 동안 반복하며 매일 두 꽃집을 합칠 때, 영재의 이동을 모두 아는 두 사람이 최선을 다하면 마지막 날 마지막 꽃을 누가 사는지 구한다.
난이도

어려움10점 중 8점

유형
게임 이론, 비트 연산, 유니온 파인드, 동적 계획법
정답자
아직 제출이 없습니다

문제

세종이와 아름이는 11부터 NN까지의 번호가 붙은 NN개의 꽃집이 있는 동네에서 데이트하고 있다. 세종이는 아름이에게 게임을 제안했다. 게임의 규칙은 다음과 같다.

  • 세종이부터 번갈아 가며 NN개의 꽃집 중 하나를 골라 그곳의 꽃을 원하는 만큼 산다. 단, 반드시 한 송이 이상의 꽃을 사야 하며, 고른 꽃집에 사고자 하는 꽃과 같은 종류의 꽃이 여러 송이 있다면 그 종류의 꽃들을 모두 사야 한다.

세종이는 마지막 남은 꽃을 자신이 사 아름이에게 주어 아름이를 두근 어질하게 만들려고 하고, 아름이 역시 같은 이유로 마지막 꽃을 자신이 사려고 한다.

그런데 꽃집을 가 보니, 모든 꽃집에 꽃이 딱 한 송이씩만 남아 있었다. 데이트가 너무 빨리 끝날 것으로 생각한 세종이와 아름이는 꽃집 주인인 영재의 도움을 구해 총 NN일에 걸쳐 매일 한 번씩 게임을 진행하기로 했다. 첫날은 세종이부터 게임을 시작하고, 그다음 날부터는 직전 날에 마지막 꽃을 가져간 사람부터 게임을 시작한다. 매일 게임이 끝나면 세종이와 아름이는 꽃을 꽃집에 돌려놓는다. 영재는 매일 게임이 끝난 뒤 꽃이 있는 꽃집 중 하나를 골라 그곳에 있는 모든 꽃을 꽃이 있는 다른 꽃집으로 옮긴다. 이를 반복해, NN번째 게임에서 마지막 꽃을 산 사람이 고백하는 것으로 데이트를 마무리한다. 두 사람은 영재가 어떻게 꽃을 옮길지 모두 알고 있으며, 데이트 마지막 날에 마지막 꽃을 가져가기 위해 최선을 다할 것이다.

세종이와 아름이 중 누가 데이트 마지막 날에 마지막 꽃을 사 상대를 두근 어질하게 만들지 알아내자!

입력

첫째 줄에 꽃집의 수 NN이 주어진다. (1≤N≤100,000)(1\leq N\leq 100\\, 000)

둘째 줄에 NN개의 정수 f_1,f_2,⋯ ,f_Nf\_1,f\_2,\cdots ,f\_N 이 공백으로 구분되어 주어진다. 이때 f_if\_i는 첫날 ii번째 꽃집에 있는 꽃의 종류를 의미한다. (1≤f_i≤108)(1\leq f\_i\leq 10^{8})

셋째 줄부터 N−1N-1개의 줄에 걸쳐, (i+2)(i+2)째 줄에 ii번째 게임이 끝난 후 영재가 꽃을 옮길 두 꽃집의 번호가 u vu\ v의 형식으로 주어진다. 이는 uu번 꽃집의 꽃들을 vv번 꽃집으로 옮기는 것을 의미한다. 항상 두 꽃집 모두 꽃이 있는 경우만 입력으로 주어진다. (1≤u,v≤N;(1\le u,v\le N; u≠v)u\neq v)

출력

세종이가 고백하게 된다면 Sejong을, 아름이가 고백하게 된다면 Areum을 출력한다.

예제2

  1. 예제 1

    입력
    5
    1 2 3 4 5
    1 2
    2 3
    3 4
    4 5
    
    예상 출력
    Sejong
    
  2. 예제 2

    입력
    4
    1 2 1 3
    1 2
    3 4
    4 2
    
    예상 출력
    Areum