N개의 정점으로 이루어진 연결 무방향 그래프가 주어진다. 그래프의 정점은 1번부터 N번까지 번호가 매겨져 있다. 이 그래프의 정점 개수와 간선의 개수는 같다. 또, 그래프의 각 정점에는 값이 하나 있는데, i번 정점의 값은 Vi이다.</p>

단순 경로란 같은 정점을 두 번 이상 방문하지 않은 경로를 의미한다. 모든 단순 경로에 대해서, 등장한 정점의 값을 순서대로 적어볼 수 있다. 이러한 수열을 단순 경로의 수열이라고 한다.

수열 S의 도치의 개수는 i < j이면서 S[i] > S[j]인 쌍 (i, j)의 개수와 같다. 예를 들어, S = {10, 30, 20, 20} 인 경우에는, 도치가 (2, 3), (2, 4)로 총 2개 있다.

그래프 G와 정수 K가 주어진다. 이때, K개 이상으로 이루어진 모든 단순 경로 중에서 단순 경로의 수열의 도치의 개수가 가장 작은 것을 찾는 프로그램을 작성하시오.

입력 형식

첫째 줄에 정점의 개수 N(3 ≤ N ≤ 1,000)과 K(1 ≤ K ≤ N)이 주어진다.</p>

둘째 줄부터 N개의 줄에는 간선의 정보가 주어진다. 간선의 정보는 두 정수로 이루어져 있으며, 루프나 같은 간선이 여러 번 주어지는 경우는 없다.

마짖막 줄에는 V가 V₁부터 V_N까지 순서대로 주어진다. (1 ≤ V_i ≤ 1,000)

출력 형식

길이가 K이상인 모든 단순 경로 중에서 단순 경로의 수열의 도치의 개수가 가장 작은 것을 출력한다. 만약, 길이가 K이상인 단순 경로가 없으면 -1을 출력한다.

예제 입력 1

3 3
1 2
2 3
3 1
40 50 60

예제 출력 1

0

예제 입력 2

4 3
1 2
2 3
3 4
4 1
60 40 50 30

예제 출력 2

1

예제 입력 3

5 5
1 2
2 3
3 4
4 1
1 5
10 10 10 5 5

예제 출력 3

1

예제 입력 4

6 6
1 2
2 3
3 4
4 1
1 5
3 6
10 2 5 3 7 1

예제 출력 4

-1

예제 입력 5

8 6
6 3
8 1
8 3
6 1
6 2
8 5
7 8
5 4
15 10 5 30 22 10 5 2

예제 출력 5

3