일감호에 다리 놓기
시간 제한2초메모리 제한256 MB
N개의 건물이 원형으로 있고 일부 인접 구간이 공사 중일 때, 모든 건물이 서로 연결되도록 하는 데 필요한 돌의 최소 개수가 K 이하인지 판정한다.
문제
학교의 홍보대사를 맡게 된 건덕이는 건국대학교의 모든 강의동을 신입생들에게 소개해야 한다.
건국대학교 중앙에 위치한 일감호를 따라 한 바퀴를 돌며 모든 강의동을 소개하는 것이 그의 일이지만, 몇몇 구간이 공사 중이어서 그 구간을 지나갈 수 없다. 급한 대로 건덕이는 호수에 돌을 던져 징검다리를 놓아 길을 만들려고 한다.
강의동은 일감호 둘레를 따라 원형으로 배치되어 있고, 강의동 양옆의 강의동은 서로 이웃한다. 또 원형으로 배치되어 있기 때문에 N개의 강의동이 있다면 N번째 강의동과 1번째 강의동은 서로 이웃한다.
일감호 안에는 와우도라는 섬이 있다. 건덕이는 한 강의동에서 다른 모든 강의동으로 이동할 수 있도록 강의동에서 와우도까지 징검다리를 놓기로 했다. 하지만 건덕이의 눈에는 K개의 돌밖에 보이지 않는다. 건덕이는 주어진 돌을 활용해서 징검다리를 완성할 수 있을까?
입력
첫째 줄에 강의동의 수 N, 공사구간의 수 M, 건덕이가 가진 돌의 수 K가 공백으로 구분되어 주어진다. 강의동은 1동부터 N동까지 존재한다.
다음 줄에는 강의동에서 와우도까지 놓아야 하는 돌의 개수 S1, S2, ..., SN이 공백으로 구분되어 주어진다. 이는 T번째 강의동에서 와우도까지 ST개의 돌을 놓아야 함을 의미한다. 이어서 M개의 줄에 i, j가 주어진다. 이는 i번째 강의동에서 j번째 강의동으로 가는 길이 공사 중임을 의미한다. 이때 입력되는 i, j번째 강의동은 서로 이웃한 강의동이다. 공사 중인 구간은 한 번만 주어진다.
출력
건덕이가 가지고 있는 돌을 놓아 모든 강의동을 연결할 수 있으면 YES를, 그렇지 않으면 NO를 출력한다.
제한
- 3 ≤ N ≤ 1,000,000
- 0 ≤ M ≤ N
- 1 ≤ i, j ≤ N
- 1 ≤ T ≤ N인 모든 정수 T에 대해 1 ≤ ST ≤ 1,000,000
- 0 ≤ K ≤ 5,000,000,000