시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 3 2 2 100.000%

문제

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

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

수열 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)이 주어진다.

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

마짖막 줄에는 V가 V1부터 VN까지 순서대로 주어진다. (1 ≤ Vi ≤ 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

출처