LED 회로에 전원 연결하기

여러분은 ACM ICPC 폐막식을 준비하는 담당자입니다. 강당을 화려하게 꾸미려고 감성이 넘치는 완벽주의자 디자이너를 고용했습니다.

몇 시간 뒤, 폐막식이 시작하기 몇 시간 전에 디자이너가 장식을 끝냈다고 알려 옵니다. 강당에 도착해 보니 묘하게 생긴 회로가 놓여 있습니다. 디자이너는 삶의 의미와 회로 곳곳에 숨겨 둔 ACM ICPC를 설명하기 시작합니다. 이 회로가 아주 잘 작동한다며 자부심도 드러냅니다. 여러분은 "이 장식이 작동하지 않으면 폐막식을 완전히 망칩니다"라고 말하며 전원을 찾습니다.

여러분: 전원은 어디 있나요?

디자이너: 네? 이건 제가 담당하는 부분이 아닙니다! 전원을 공급해야 하는 사람은 당신입니다. 그리고 회로는 절대 건드리지 마세요! 접점에 전원만 연결하면 됩니다. 저는 매니저에게 이 완벽한 작업을 보고해야겠군요. 그럼 이만.

LED의 구조: 어노드(Anode)와 캐소드(Cathode)

여러분은 덩그러니 남겨진 회로를 조사합니다.

극성과 무관하게 빛나는 보통 전구와 달리, LED는 극성이 올바를 때만, 즉 어노드 핀의 전압이 캐소드 핀의 전압보다 높을 때만 빛납니다. LED에는 최소 전압이 있어서, 방향을 올바르게 연결해도 걸리는 전압이 최소 전압보다 낮으면 켜지지 않습니다. 최대 전압도 있어서, 걸리는 전압이 최대 전압보다 높으면 소자가 타 버립니다.

회로를 확인해 보니 구성품은 세 가지였습니다.

LED: 회로의 LED는 모두 같은 종류라서 최소 전압과 최대 전압이 서로 같다.
접점: LED의 두 핀은 접점에 연결된다. 접점은 LED의 핀뿐 아니라 전선의 끝점도 연결한다.
전선: 전선마다 끝점이 두 개 있고, 두 끝점은 각각 접점에 연결되어 전압을 전달한다.

전압이 서로 다른 외부 극을 접점에 연결하면 회로에 전압을 공급할 수 있습니다. 주의할 점은 합선입니다. 각 전선의 두 끝점은 반드시 같은 전압에 연결되어야 합니다. 전자기학에서는 보통 최소 전위를 0으로 잡으므로, 모든 전압은 음수가 아니라고 보아도 됩니다.

이제 회로에 맞는 전원 공급기를 사야 합니다. 전원 공급기의 가격은 공급할 수 있는 최대 전압에 비례합니다.

LED 회로의 정보가 주어질 때, 합선을 내지 않고 LED를 태우지도 않으면서 모든 LED를 켤 수 있는지 판정하는 프로그램을 작성하세요. 켤 수 있다면 모든 LED를 켜는 최대 전압의 최솟값까지 구해야 합니다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 다섯 개의 정수 $J$ , $L$ , $W$ , $m$ , $M$ 이 공백으로 구분되어 주어진다. $J$ 는 접점의 개수 ( $2 \le J \le 500$ ), $L$ 은 LED의 개수 ( $1 \le L \le 5000$ ), $W$ 는 전선의 개수 ( $0 \le W \le 5000$ )이고, $m$ 과 $M$ 은 각각 LED의 최소 전압과 최대 전압이다 ( $1 \le m < M \le 1000$ ). 접점에는 $1$ 부터 $J$ 까지 번호가 붙어 있다.

다음 $L$ 개의 줄에는 두 정수가 공백으로 구분되어 주어진다. 첫 번째 정수는 LED의 어노드 핀이 연결된 접점의 번호, 두 번째 정수는 캐소드 핀이 연결된 접점의 번호다.

그다음 $W$ 개의 줄에는 전선이 잇는 두 접점의 번호가 두 정수로 주어진다.

0 0 0 0 0이 입력되면 입력이 끝난다.

LED 회로에 전원 연결하기

문제

입력

출력

힌트