만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

두근 어질

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

요약
두 사람이 꽃집에서 꽃 종류를 번갈아 가져가는 게임을 N일 동안 진행하며, 매일 꽃집 하나의 꽃이 다른 꽃집으로 합쳐질 때 마지막 날 마지막 꽃을 가져가는 사람을 구합니다.
난이도

보통10점 중 7점

유형
게임 이론, 해시맵, 유니온 파인드
정답자
아직 제출이 없습니다

문제

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

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

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

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

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

입력

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

둘째 줄에 NN개의 정수 f1,f2,⋯ ,fNf_1, f_2, \cdots, f_N이 공백으로 구분되어 주어진다. fif_i는 첫날 ii번째 꽃집에 있는 꽃의 종류를 의미한다. (1≤fi≤108)(1 \le f_i \le 10^8)

셋째 줄부터 N−1N-1개의 줄에 걸쳐, (i+2)(i+2)번째 줄에 ii번째 게임이 끝난 후 영재가 꽃을 옮길 두 꽃집의 번호가 uu vv의 형식으로 주어진다. 이는 uu번 꽃집의 꽃들을 vv번 꽃집으로 옮긴다는 뜻이다. 입력에는 항상 두 꽃집 모두 꽃이 있는 경우만 주어진다. (1≤u,v≤N(1 \le u, v \le N, u≠v)u \ne 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