아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

트리 게임

면접 대비

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

요약
트리에서 시작 정점 S와 목표 정점 E가 주어질 때, E를 방문해야 하는 말 이동 게임에서 선공과 후공 중 누가 이기는지 판정한다.
난이도

보통10점 중 7점

유형
게임 이론, 트리, DFS, 그래프
정답자
아직 제출이 없습니다

문제

트리 게임은 정점 NN개, 간선 N−1N-1개로 이루어진 트리 위에서 진행되는 게임입니다. 각 정점은 11 이상 NN 이하의 번호를 하나씩 가집니다.

트리 위에는 11개의 말이 있는데, 각 플레이어는 자신의 턴에 간선으로 이어진 인접한 정점으로 말을 옮겨야 합니다. 단, 한 번 방문했던 정점으로는 이동할 수 없으며, 더는 말을 움직일 수 없게 되면 게임이 종료됩니다. 이때 게임 진행 과정에서 한 번이라도 말이 목표 정점 EE를 방문했다면 선공의 승리이고, 그렇지 못하면 후공의 승리입니다.

기말고사 공부가 너무도 하기 싫었던 태호와 윤아는 트리 게임만 수천 판을 해버렸고, 결국 트리 게임의 최선의 전략을 터득해 버렸습니다. 더는 기말고사 공부를 미룰 수 없었던 태호와 윤아는 마지막 승부를 내기로 했고, 가위바위보를 이긴 윤아가 선/후공 결정권을 가져왔습니다.

이때 윤아가 게임에서 승리하려면 선공, 후공 중 어느 것을 골라야 할까요?

단, 태호와 윤아는 최선의 전략을 이미 알고 있고, 최적의 방법으로 게임에 임한다고 가정합니다.

입력

첫째 줄에 정점의 개수 N(2≤N≤100,000)N (2≤N≤100,000)과 말의 시작 정점 SS, 목표 정점 E(1≤S,E≤N,S≠E)E (1≤S, E≤N, S≠E)가 주어집니다. 다음 N−1N-1개의 줄에 걸쳐서 트리의 각 간선이 잇는 두 정점의 번호 u,v(1≤u,v≤N,u≠v)u, v (1≤u, v≤N, u≠v)가 주어집니다.

출력

윤아가 게임에서 승리하기 위해 선공을 골라야 하면 First를, 후공을 골라야 하면 Second를 출력해주세요.

예제2

  1. 예제 1

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

    입력
    6 1 5
    1 2
    1 3
    3 6
    4 1
    3 5
    
    예상 출력
    Second