시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 3204 572 417 22.812%

문제

아주 먼 미래에 사람들이 가장 많이 사용하는 대중교통은 하이퍼튜브이다. 하이퍼튜브 하나는 역 K개를 서로 연결한다. 1번역에서 N번역으로 가는데 방문하는 최소 역의 수는 몇 개일까?

입력

첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000)

다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어진다. 총 K개 숫자가 주어지며, 이 숫자는 그 하이퍼튜브가 서로 연결하는 역의 번호이다. 

출력

첫째 줄에 1번역에서 N번역으로 가는데 방문하는 역의 개수의 최솟값을 출력한다. 만약, 갈 수 없다면 -1을 출력한다.

예제 입력 1

9 3 5
1 2 3
1 4 5
3 6 7
5 6 7
6 8 9

예제 출력 1

4

힌트

1-3-6-9나 1-5-6-9로 이동하면 된다.

W3sicHJvYmxlbV9pZCI6IjUyMTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ2NThcdWMyYjkiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzU0NFx1YzhmYyBcdWJhM2MgXHViYmY4XHViNzk4XHVjNWQwIFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc3NCBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzc0IFx1YzBhY1x1YzZhOVx1ZDU1OFx1YjI5NCBcdWIzMDBcdWM5MTFcdWFkNTBcdWQxYjVcdWM3NDAgXHVkNTU4XHVjNzc0XHVkMzdjXHVkMjljXHViZTBjXHVjNzc0XHViMmU0LiBcdWQ1NThcdWM3NzRcdWQzN2NcdWQyOWNcdWJlMGMgXHVkNTU4XHViMDk4XHViMjk0IFx1YzVlZCBLXHVhYzFjXHViOTdjIFx1YzExY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWQ1NWNcdWIyZTQuIDFcdWJjODhcdWM1ZWRcdWM1ZDBcdWMxMWMgTlx1YmM4OFx1YzVlZFx1YzczY1x1Yjg1YyBcdWFjMDBcdWIyOTRcdWIzNzAgXHViYzI5XHViYjM4XHVkNTU4XHViMjk0IFx1Y2Q1Y1x1YzE4YyBcdWM1ZWRcdWM3NTggXHVjMjE4XHViMjk0IFx1YmE4NyBcdWFjMWNcdWM3N2NcdWFlNGM/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzVlZFx1Yzc1OCBcdWMyMTggTlx1YWNmYyBcdWQ1NWMgXHVkNTU4XHVjNzc0XHVkMzdjXHVkMjljXHViZTBjXHVhYzAwIFx1YzExY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVjNWVkXHVjNzU4IFx1YWMxY1x1YzIxOCBLLCBcdWQ1NThcdWM3NzRcdWQzN2NcdWQyOWNcdWJlMGNcdWM3NTggXHVhYzFjXHVjMjE4IE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxMDAsMDAwLCAxICZsZTsgSywgTSAmbGU7IDEwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBNXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ1NThcdWM3NzRcdWQzN2NcdWQyOWNcdWJlMGNcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjZDFkIEtcdWFjMWMgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVjNzc0IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWFkZjggXHVkNTU4XHVjNzc0XHVkMzdjXHVkMjljXHViZTBjXHVhYzAwIFx1YzExY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVjNWVkXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yzc3NFx1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIDFcdWJjODhcdWM1ZWRcdWM1ZDBcdWMxMWMgTlx1YmM4OFx1YzVlZFx1YzczY1x1Yjg1YyBcdWFjMDBcdWIyOTRcdWIzNzAgXHViYzI5XHViYjM4XHVkNTU4XHViMjk0IFx1YzVlZFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWFjMDggXHVjMjE4IFx1YzVjNlx1YjJlNFx1YmE3NCAtMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPjEtMy02LTlcdWIwOTggMS01LTYtOVx1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTIxNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkhJUEVSQ0lKRVZJIiwiZGVzY3JpcHRpb24iOiI8cD5JbiBhIGdhbGF4eSBmYXIsIGZhciBhd2F5LCB0aGUgZmFzdGVzdCBtZXRob2Qgb2YgdHJhbnNwb3J0YXRpb24gaXMgdXNpbmcgaHlwZXJ0dWJlcy4gRWFjaCBoeXBlcnR1YmUgZGlyZWN0bHkgY29ubmVjdHMgSyBzdGF0aW9ucyB3aXRoIGVhY2ggb3RoZXIuIFdoYXQgaXMgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHN0YXRpb25zIHRoYXQgd2UgbmVlZCB0byBwYXNzIHRocm91Z2ggaW4gb3JkZXIgdG8gZ2V0IGZyb20gc3RhdGlvbiAxIHRvIHN0YXRpb24gTj88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRocmVlIHBvc2l0aXZlIGludGVnZXJzOiBOICgxICZsZTsgTiAmbGU7IDEwMCAwMDApLCB0aGUgbnVtYmVyIG9mIHN0YXRpb25zLCBLICgxICZsZTsgSyAmbGU7IDEgMDAwKSwgdGhlIG51bWJlciBvZiBzdGF0aW9ucyB0aGF0IGFueSBzaW5nbGUgaHlwZXJ0dWJlIGRpcmVjdGx5IGludGVyY29ubmVjdHMsIGFuZCBNICgxICZsZTsgTSAmbGU7IDEgMDAwKSwgdGhlIG51bWJlciBvZiBoeXBlcnR1YmVzLjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTSBsaW5lcyBjb250YWlucyB0aGUgZGVzY3JpcHRpb24gb2YgYSBzaW5nbGUgaHlwZXJ0dWJlOiBLIHBvc2l0aXZlIGludGVnZXJzLCB0aGUgbGFiZWxzIG9mIHN0YXRpb25zIGNvbm5lY3RlZCB0byB0aGF0IGh5cGVydHViZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSByZXF1aXJlZCBtaW5pbXVtIG51bWJlciBvZiBzdGF0aW9ucy4gSWYgaXQgaXNuJiMzOTt0IHBvc3NpYmxlIHRvIHRyYXZlbCBmcm9tIHN0YXRpb24gMSB0byBzdGF0aW9uIE4sIG91dHB1dCAtMS48XC9wPlxyXG4iLCJoaW50IjoiPHA+SXQgaXMgcG9zc2libGUgdG8gdHJhdmVsIGZyb20gc3RhdGlvbiAxIHRvIHN0YXRpb24gOSB1c2luZyBvbmx5IGZvdXIgc3RhdGlvbnMgaW4gdGhlIGZvbGxvd2luZyB3YXlzOiAxLTMtNi05LCBvciAxLTUtNi05LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #5 4번