윤이는 엄청난 것을 훔쳐 갔습니다
시간 제한1초메모리 제한1024 MB
나무 모양의 마을에서 윤이 정점 a에서 출발해 경찰 b, c에게 잡히지 않고 리프 노드에 도달할 수 있는지 판별합니다.
문제
UDP 마을의 경찰인 달구와 포닉스는 윤이를 잡으러 출동했다. UDP 마을은 개의 정점으로 이루어진 트리이다. 트리는 개의 정점과 개의 간선으로 이루어진 연결 그래프다. 이웃한 정점이 하나뿐인 정점을 리프 노드라고 한다.
트리의 각 정점에는 1번부터 번까지 번호가 붙어 있다. 윤이는 정점 에서 출발하고, 달구와 포닉스는 각각 정점 , 에서 출발한다. 세 정점은 서로 다르다. 윤이, 달구, 포닉스는 다음 순서로 번갈아 이동하며 추격전을 벌인다. 한 정점에 둘 이상이 있어도 된다.
- 윤이가 간선을 따라 이웃한 정점으로 이동한다.
- 이어서 달구와 포닉스가 각각 간선을 따라 이웃한 정점으로 이동한다.
윤이가 경찰과 같은 정점에 놓이면 즉시 잡힌다. 반면 잡히지 않고 리프 노드에 도달하면 즉시 이웃한 마을로 탈출할 수 있다. 윤이가 리프 노드에서 출발하는 경우도 마찬가지다.
윤이, 달구, 포닉스가 최선의 전략으로 추격전을 벌일 때, 윤이는 무사히 탈출할 수 있을까?
입력
첫 번째 줄에 UDP 마을의 정점 개수 이 주어진다. ()
다음 개의 줄에 트리의 간선 정보를 나타내는 정수 , 가 주어진다. 정점 와 사이에 간선이 있다는 뜻이다. ()
마지막 줄에 윤이, 달구, 포닉스의 위치를 나타내는 정수 , , 가 주어진다. (; , , 는 서로 다르다.)
출력
윤이가 탈출할 수 있으면 YES, 그렇지 않으면 NO를 출력한다.