단순 경로 수열의 도치

정점이 $N$개인 연결 무방향 그래프가 주어진다. 정점에는 $1$번부터 $N$번까지 번호가 붙어 있고, 간선의 개수는 정점의 개수와 같다. $i$번 정점에는 값 $V_i$가 하나 적혀 있다.

같은 정점을 두 번 이상 지나지 않는 경로를 단순 경로라고 한다. 단순 경로가 지나는 정점의 값을 지나는 순서대로 적으면 수열이 하나 나온다. 이 수열을 그 단순 경로의 수열이라고 한다. 정점 하나로만 이루어진 경로도 단순 경로다.

수열 $S$의 도치의 개수는 $i < j$이면서 $S[i] > S[j]$인 쌍 $(i, j)$의 개수다. 예를 들어 $S = (10, 30, 20, 20)$이면 도치는 $(2, 3)$과 $(2, 4)$로 두 개다.

그래프와 정수 $K$가 주어진다. 정점을 $K$개 이상 지나는 모든 단순 경로 중에서 수열의 도치 개수가 가장 작은 값을 구하는 프로그램을 작성하시오.

첫째 줄에 정점의 개수 $N$과 정수 $K$가 주어진다. ($3 \le N \le 1000$, $1 \le K \le N$)

둘째 줄부터 $N$개의 줄에 간선의 정보가 한 줄에 하나씩 주어진다. 각 줄에는 간선이 잇는 두 정점의 번호가 주어진다. 자기 자신으로 이어지는 간선은 없고, 같은 간선이 두 번 주어지지도 않는다.

마지막 줄에 $V_1$부터 $V_N$까지 $N$개의 값이 순서대로 주어진다. ($1 \le V_i \le 1000$)

정점을 $K$개 이상 지나는 모든 단순 경로 중에서 수열의 도치 개수가 가장 작은 값을 첫째 줄에 출력한다. 그런 단순 경로가 없으면 -1을 출력한다.