만드는 중입니다

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

윤이는 엄청난 것을 훔쳐 갔습니다

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

요약
나무 모양의 마을에서 윤이 정점 a에서 출발해 경찰 b, c에게 잡히지 않고 리프 노드에 도달할 수 있는지 판별합니다.
난이도

어려움10점 중 8점

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

문제

UDP 마을의 경찰인 달구와 포닉스는 윤이를 잡으러 출동했다. UDP 마을은 NN개의 정점으로 이루어진 트리이다. 트리는 NN개의 정점과 N−1N-1개의 간선으로 이루어진 연결 그래프다. 이웃한 정점이 하나뿐인 정점을 리프 노드라고 한다.

트리의 각 정점에는 1번부터 NN번까지 번호가 붙어 있다. 윤이는 정점 aa에서 출발하고, 달구와 포닉스는 각각 정점 bb, cc에서 출발한다. 세 정점은 서로 다르다. 윤이, 달구, 포닉스는 다음 순서로 번갈아 이동하며 추격전을 벌인다. 한 정점에 둘 이상이 있어도 된다.

  • 윤이가 간선을 따라 이웃한 정점으로 이동한다.
  • 이어서 달구와 포닉스가 각각 간선을 따라 이웃한 정점으로 이동한다.

윤이가 경찰과 같은 정점에 놓이면 즉시 잡힌다. 반면 잡히지 않고 리프 노드에 도달하면 즉시 이웃한 마을로 탈출할 수 있다. 윤이가 리프 노드에서 출발하는 경우도 마찬가지다.

윤이, 달구, 포닉스가 최선의 전략으로 추격전을 벌일 때, 윤이는 무사히 탈출할 수 있을까?

입력

첫 번째 줄에 UDP 마을의 정점 개수 NN이 주어진다. (3≤N≤200 0003\le N\le 200\ 000)

다음 N−1N-1개의 줄에 트리의 간선 정보를 나타내는 정수 uu, vv가 주어진다. 정점 uu와 vv 사이에 간선이 있다는 뜻이다. (1≤u,v≤N1\le u,v\le N)

마지막 줄에 윤이, 달구, 포닉스의 위치를 나타내는 정수 aa, bb, cc가 주어진다. (1≤a,b,c≤N1\le a,b,c\le N; aa, bb, cc는 서로 다르다.)

출력

윤이가 탈출할 수 있으면 YES, 그렇지 않으면 NO를 출력한다.

예제2

  1. 예제 1

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

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