시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
9 초 256 MB 89 22 16 25.806%

문제

외판원 현우는 자신의 직업에 불만이 많다. 그래서 현우는 외판원도 아니고 왜판원이다.

외판원 문제는 그래프에서 모든 정점을 방문하여 시작점으로 돌아오는 최단경로를 찾아야 하는 유명한 문제이다. 왜판원 문제의 목표는 조금 다르다. 정점의 개수가 N개인 그래프에서 역시 모든 정점을 방문하여 시작점으로 돌아오되, 정확히 그 길이가 L인 경로가 존재하는지를 알아내야 한다. 다시 말해서, 경로의 길이가 L이고 크기가 N인 싸이클이 존재하는지를 알아내야 한다.

입력

첫째 줄에 정점의 개수 N과 목표로 하는 거리 L이 주어진다(2 ≤ N ≤ 14, L (1 ≤ L ≤ 1015).

이어서 N개의 줄에 걸쳐, 정점 i, j 사이의 거리 dij가 i번째 줄의 j번째 값으로 주어진다(i ≠ j이면 1 ≤ dij ≤ L, 모든 i에 대해 dii = 0). 모든 정점 1 ≤ i, j, k ≤ N에 대해 dij = dji이고 dij ≤ dik + dkj이다.

출력

첫째 줄에 길이가 L이고 크기가 N인 싸이클이 존재한다면 "possible", 그렇지 않다면 "impossible"을 큰따옴표 없이 출력한다.

예제 입력

4 10
0 3 2 1
3 0 1 3
2 1 0 2
1 3 2 0

예제 출력

possible

예제 입력 2

3 5
0 1 2
1 0 3
2 3 0

예제 출력 2

impossible

힌트