시간 제한메모리 제한제출정답맞힌 사람정답 비율
9 초 256 MB76117912022.857%

문제

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

외판원 문제는 그래프에서 모든 정점을 방문하여 시작점으로 돌아오는 최단경로를 찾아야 하는 유명한 문제이다. 왜판원 문제의 목표는 조금 다르다. 정점의 개수가 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"을 큰따옴표 없이 출력한다.

예제 입력 1

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

예제 출력 1

possible

예제 입력 2

3 5
0 1 2
1 0 3
2 3 0

예제 출력 2

impossible
W3sicHJvYmxlbV9pZCI6IjEwNTI2IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNjVjXHVkMzEwXHVjNmQwIFx1YzIxY1x1ZDY4YyIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNjc4XHVkMzEwXHVjNmQwIFx1ZDYwNFx1YzZiMFx1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NTggXHVjOWMxXHVjNWM1XHVjNWQwIFx1YmQ4OFx1YjljY1x1Yzc3NCBcdWI5Y2VcdWIyZTQuIFx1YWRmOFx1Yjc5OFx1YzExYyBcdWQ2MDRcdWM2YjBcdWIyOTQgXHVjNjc4XHVkMzEwXHVjNmQwXHViM2M0IFx1YzU0NFx1YjJjOFx1YWNlMCBcdWM2NWNcdWQzMTBcdWM2ZDBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzY3OFx1ZDMxMFx1YzZkMCBcdWJiMzhcdWM4MWNcdWIyOTQgXHVhZGY4XHViNzk4XHVkNTA0XHVjNWQwXHVjMTFjIFx1YmFhOFx1YjRlMCBcdWM4MTVcdWM4MTBcdWM3NDQgXHViYzI5XHViYjM4XHVkNTU4XHVjNWVjIFx1YzJkY1x1Yzc5MVx1YzgxMFx1YzczY1x1Yjg1YyBcdWIzY2NcdWM1NDRcdWM2MjRcdWIyOTQgXHVjZDVjXHViMmU4XHVhY2JkXHViODVjXHViOTdjIFx1Y2MzZVx1YzU0NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjNzIwXHViYTg1XHVkNTVjIFx1YmIzOFx1YzgxY1x1Yzc3NFx1YjJlNC4gXHVjNjVjXHVkMzEwXHVjNmQwIFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWJhYTlcdWQ0NWNcdWIyOTQgXHVjODcwXHVhZTA4IFx1YjJlNFx1Yjk3NFx1YjJlNC4gXHVjODE1XHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBOXHVhYzFjXHVjNzc4IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1YzVkMFx1YzExYyBcdWM1ZWRcdWMyZGMgXHViYWE4XHViNGUwIFx1YzgxNVx1YzgxMFx1Yzc0NCBcdWJjMjlcdWJiMzhcdWQ1NThcdWM1ZWMgXHVjMmRjXHVjNzkxXHVjODEwXHVjNzNjXHViODVjIFx1YjNjY1x1YzU0NFx1YzYyNFx1YjQxOCwgXHVjODE1XHVkNjU1XHVkNzg4IFx1YWRmOCBcdWFlMzhcdWM3NzRcdWFjMDAgTFx1Yzc3OCBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0XHVjOWMwXHViOTdjIFx1YzU0Y1x1YzU0NFx1YjBiNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjJlNFx1YzJkYyBcdWI5ZDBcdWQ1NzRcdWMxMWMsIFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgTFx1Yzc3NFx1YWNlMCBcdWQwNmNcdWFlMzBcdWFjMDAgTlx1Yzc3OCBcdWMyZjhcdWM3NzRcdWQwNzRcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0XHVjOWMwXHViOTdjIFx1YzU0Y1x1YzU0NFx1YjBiNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMTggTlx1YWNmYyBcdWJhYTlcdWQ0NWNcdWI4NWMgXHVkNTU4XHViMjk0IFx1YWM3MFx1YjlhYyBMXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNCgyICZsZTsgTiAmbGU7IDE0LCBMICgxICZsZTsgTCAmbGU7IDEwPHN1cD4xNTxcL3N1cD4pLjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWM1YjRcdWMxMWMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwLCBcdWM4MTVcdWM4MTAgaSwgaiBcdWMwYWNcdWM3NzRcdWM3NTggXHVhYzcwXHViOWFjIGQ8c3ViPmlqPFwvc3ViPlx1YWMwMCBpXHViYzg4XHVjOWY4IFx1YzkwNFx1Yzc1OCBqXHViYzg4XHVjOWY4IFx1YWMxMlx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQoaSAmbmU7IGpcdWM3NzRcdWJhNzQgMSAmbGU7IGQ8c3ViPmlqPFwvc3ViPiAmbGU7IEwsIFx1YmFhOFx1YjRlMCBpXHVjNWQwIFx1YjMwMFx1ZDU3NCBkPHN1Yj5paTxcL3N1Yj4gPSAwKS4gXHViYWE4XHViNGUwIFx1YzgxNVx1YzgxMCAxICZsZTsgaSwgaiwgayAmbGU7IE5cdWM1ZDAgXHViMzAwXHVkNTc0IGQ8c3ViPmlqPFwvc3ViPiA9IGQ8c3ViPmppPFwvc3ViPlx1Yzc3NFx1YWNlMCBkPHN1Yj5pajxcL3N1Yj4gJmxlOyBkPHN1Yj5pazxcL3N1Yj4gKyBkPHN1Yj5rajxcL3N1Yj5cdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFlMzhcdWM3NzRcdWFjMDAgTFx1Yzc3NFx1YWNlMCBcdWQwNmNcdWFlMzBcdWFjMDAgTlx1Yzc3OCBcdWMyZjhcdWM3NzRcdWQwNzRcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0XHViYTc0ICZxdW90O3Bvc3NpYmxlJnF1b3Q7LCBcdWFkZjhcdWI4MDdcdWM5YzAgXHVjNTRhXHViMmU0XHViYTc0ICZxdW90O2ltcG9zc2libGUmcXVvdDtcdWM3NDQgXHVkMDcwXHViNTMwXHVjNjM0XHVkNDVjIFx1YzVjNlx1Yzc3NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTA1MjYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJJbmRvb3JpZW50ZWVyaW5nIiwiZGVzY3JpcHRpb24iOiI8cD5MdWsmYWFjdXRlOyZzY2Fyb247IHJlYWxseSBsaWtlcyBvcmllbnRlZXJpbmcsIGEgc3BvcnQgdGhhdCByZXF1aXJlcyBsb2NhdGluZyBjb250cm9sIHBvaW50cyBpbiByb3VnaCB0ZXJyYWluLiBUbyBlbnRlcnRhaW4gdGhlIE5XRVJDIHBhcnRpY2lwYW50cyBMdWsmYWFjdXRlOyZzY2Fyb247IHdhbnRzIHRvIG9yZ2FuaXplIGFuIG9yaWVudGVlcmluZyByYWNlLiBIb3dldmVyLCBpdCB3b3VsZCBiZSB0b28gaGFyc2ggZm9yIHRoZSBwYXJ0aWNpcGFudHMgdG8gYmUgb3V0ZG9vcnMgaW4gdGhpcyBjb2xkIFN3ZWRpc2ggTm92ZW1iZXIgd2VhdGhlciwgc28gaGUgZGVjaWRlZCB0byBqdW1wIG9uIHRoZSBuZXcgdHJlbmQgb2YgaW5kb29yIHJhY2VzLCBhbmQgc2V0IHRoZSByYWNlIGluc2lkZSB0aGUgQiBidWlsZGluZyBvZiBMaW5rJm91bWw7cGluZyBVbml2ZXJzaXR5LjxcL3A+XHJcblxyXG48cD5MdWsmYWFjdXRlOyZzY2Fyb247IGhhcyBhbHJlYWR5IGRlY2lkZWQgb24gdGhlIGxvY2F0aW9ucyBvZiB0aGUgY29udHJvbCBwb2ludHMuIEhlIGhhcyBhbHNvIGRlY2lkZWQgb24gdGhlIGV4YWN0IGxlbmd0aCBvZiB0aGUgcmFjZSwgc28gdGhlIG9ubHkgdGhpbmcgcmVtYWluaW5nIGlzIHRvIGRlY2lkZSBpbiB3aGljaCBvcmRlciB0aGUgY29udHJvbCBwb2ludHMgc2hvdWxkIGJlIHZpc2l0ZWQgc3VjaCB0aGF0IHRoZSBsZW5ndGggb2YgdGhlIHRvdGFsIHJhY2UgaXMgYXMgaGUgd2lzaGVzLiBCZWNhdXNlIHRoaXMgaXMgbm90IGFsd2F5cyBwb3NzaWJsZSwgaGUgYXNrcyB5b3UgdG8gd3JpdGUgYSBwcm9ncmFtIHRvIGhlbHAgaGltLjxcL3A+XHJcblxyXG48cD48ZW0+Tm90ZSBmcm9tIHRoZSBvcmdhbml6ZXI6IHRoZSBOV0VSQyBpbmRvb3JpZW50ZWVyaW5nIHJhY2UgZm9yIHRoaXMgeWVhciBoYXMgYmVlbiBjYW5jZWxsZWQgc2luY2Ugd2UgbmVnbGVjdGVkIHRvIGFwcGx5IGZvciBhbiBvcmllbnRlZXJpbmcgcGVybWl0IGluIHRpbWUgZnJvbSB0aGUgdW5pdmVyc2l0eSBhZG1pbmlzdHJhdGlvbi4gKFdlIHN0aWxsIG5lZWQgeW91IHRvIHNvbHZlIHRoZSBwcm9ibGVtIHNvIHRoYXQgd2UgY2FuIG9yZ2FuaXplIGl0IGZvciBuZXh0IHllYXIuKTxcL2VtPjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPm9uZSBsaW5lIHdpdGggdHdvIGludGVnZXJzIG4gKDIgJmxlOyBuICZsZTsgMTQpIGFuZCBMICgxICZsZTsgTCAmbGU7IDEwPHN1cD4xNTxcL3N1cD4pLCB0aGUgbnVtYmVyIG9mIGNvbnRyb2wgcG9pbnRzIGFuZCB0aGUgZGVzaXJlZCBsZW5ndGggb2YgdGhlIHJhY2UsIHJlc3BlY3RpdmVseTs8XC9saT5cclxuXHQ8bGk+biBsaW5lcyB3aXRoIG4gaW50ZWdlcnMgZWFjaC4gVGhlIGp0aCBpbnRlZ2VyIG9uIHRoZSBpdGggbGluZSwgZDxzdWI+aWo8XC9zdWI+ICwgZGVub3RlcyB0aGUgZGlzdGFuY2UgYmV0d2VlbiBjb250cm9sIHBvaW50IGkgYW5kIGogKDEgJmxlOyBkPHN1Yj5pajxcL3N1Yj4gJmxlOyBMIGZvciBpICZuZTsgaiwgYW5kIGQ8c3ViPmlpPFwvc3ViPiA9IDApLiBGb3IgYWxsIDEgJmxlOyBpLCBqLCBrICZsZTsgTiBpdCBpcyB0aGUgY2FzZSB0aGF0IGQ8c3ViPmlqPFwvc3ViPiA9IGQ8c3ViPmppPFwvc3ViPiBhbmQgZDxzdWI+aWo8XC9zdWI+ICZsZTsgZDxzdWI+aWs8XC9zdWI+ICsgZDxzdWI+a2o8XC9zdWI+IC48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBvbmUgbGluZSB3aXRoICZsZHF1bztwb3NzaWJsZSZyZHF1bzsgaWYgaXQgaXMgcG9zc2libGUgdG8gdmlzaXQgYWxsIGNvbnRyb2wgcG9pbnRzIG9uY2UgaW4gc29tZSBvcmRlciBhbmQgZGlyZWN0bHkgcmV0dXJuIHRvIHRoZSBmaXJzdCBvbmUgc3VjaCB0aGF0IHRoZSB0b3RhbCBkaXN0YW5jZSBpcyBleGFjdGx5IEwsIGFuZCAmbGRxdW87aW1wb3NzaWJsZSZyZHF1bzsgb3RoZXJ3aXNlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2014 I번

  • 문제를 번역한 사람: kks227
  • 문제를 만든 사람: Jeroen Bransen