승부조작

문제 정보

문제

한때 세계대회 준우승까지 하며 최강의 프로그래머로 칭송 받았던 J씨는 성적이 떨어진 이후 유혹을 이기지 못하고 승부 조작의 세계에 손을 댔습니다. 프로그래밍 대회의 마당발로 알려졌던 J씨인만큼 승부 조작의 규모는 상당해서, 알고스팟 컵 결승 리그에 진출한 N명의 선수 모두를 승부 조작에 참여시켰습니다.

결승 리그는 여러 번의 1:1 경기로 이루어집니다. 경기를 하면 무승부 없이 항상 승부가 나며, 모든 경기가 끝난 후 승수가 가장 많은 선수가 우승합니다. 만약 가장 승수가 많은 선수가 둘 이상 있을 경우 공동 우승을 하게 됩니다. J씨는 대부분이 우승하지 못할 것으로 점쳤던 선수 X를 단독 우승하도록 해서 도박 사이트에서 부당 이득을 챙기려 합니다. 물론 너무 노골적으로 승부를 조작하면 의심을 피하기 어렵기 때문에, 가능한 X가 적은 승수로 우승하도록 하고 싶습니다.

현재 각 선수의 승수와 남아 있는 경기의 목록이 주어질 때, 승부를 적절히 조작해 X가 우승하도록 할 수 있는지 여부를 계산하고, 우승할 수 있다면 필요한 X의 최소 승수는 얼마인지 계산하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 결승 리그에 참가하는 선수의 수 N (2 <= N <= 12) 과 남아 있는 경기의 수 M (0 <= M <= 100) 이 주어집니다. 이 때 각 선수에게는 0부터 N-1 까지의 번호가 주어집니다. 그 다음 줄에는 N 개의 정수로 0번부터 N-1 번까지 순서대로 각 선수의 현재 승수가 주어집니다. 그 후 M 줄에는 각 경기를 치르는 두 선수의 번호가 주어집니다. 모든 선수의 현재 승수는 1000 이하입니다.

선수 X의 번호는 0번입니다. 결승 리그에서 모든 선수가 같은 수의 경기를 치르도록 되어 있다는 보장은 없습니다.

출력

각 테스트 케이스마다 한 줄에 X가 리그를 단독 우승하기 위해 필요한 최소 승수를 출력합니다. 만약 이것이 불가능하다면 -1 을 출력합니다.

예제 입력

3
2 2
3 3
0 1
0 1
3 3
4 2 2
1 2
1 2
1 2
4 4
5 3 3 2
0 1 
1 2
2 3
1 3

예제 출력

5
-1
5

노트

8개의 댓글이 있습니다.