시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 202 39 24 23.762%

문제

성공한 벤쳐회사 "봉씨"의 사장 연종이는 사업을 미국으로 확장하기로 결정했다.

봉씨는 LA에 있는 투자자들을 만나기 위해 미국으로 출발했다. 하지만, 비행기를 내리고 보니 그곳은 LA가 아니었다. 연종이의 비서는 아는 미국 도시가 뉴욕밖에 없었기 때문에, 당연히 사장의 항공편을 뉴욕행으로 예약한 것이다.

연종이는 LA까지 가는 비용을 최대한 줄이려고 한다. 따라서, 그는 비행기를 타는 대신에 차를 빌려서 이동할 것이다.

미국에는 N개의 도시가 있고, 각 도시는 1번부터 N번까지 번호가 매겨져 있다. 또, M개의 도로가 있다. 도로는 두 도시를 연결하며, 한 방향으로만 움직일 수 있다.

뉴욕의 도시 번호는 1번이고, LA의 번호는 2번이다. 

연종이의 회사는 구글을 넘는 가치를 지니고 있기 때문에, 연종이가 방문하는 도시에 경호원을 고용하려고 한다. 이 때, 고용해야하는 경호원의 수를 최소화하는 프로그램을 작성하시오. 어떤 도시에서 경호원을 고용하면, 몇 번을 방문하더라도 재고용하지 않아도 된다. 연종이는 뉴욕에서 출발해서 LA를 방문했다가 다시 뉴욕으로 돌아온다.

입력

첫째 줄에는 N과 M이 주어진다. (2 ≤ N ≤ 100, 2 ≤ M ≤ 200)

다음 M개의 줄에는 서로 다른 정수 A와 B가 주어진다. (1 ≤ A, B ≤ N) 이 두 숫자는 도로에 대한 정보이고, A에서 B로 가는 도로라는 뜻이다. 같은 도로가 두 번이상 주어지는 경우는 없지만, 반대 방향 도로(B -> A)가 주어질 수는 있다.

출력

첫재 줄에 뉴욕에서 LA로 갔다가, 다시 뉴욕으로 돌아오는 경로 중 고용해야하는 경호원의 수의 최소값을 출력한다. 항상 답이 존재하는 경우만 입력으로 주어진다.

예제 입력 1

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

예제 출력 1

6

힌트

다음과 같이 이동하면 된다. 1->3->4->2->6->3->4->5->1

W3sicHJvYmxlbV9pZCI6IjI3OTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYWNcdWM1YzUgXHVkNjU1XHVjN2E1IiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWMxMzFcdWFjZjVcdWQ1NWMgXHViY2E0XHVjY2QwXHVkNjhjXHVjMGFjICZxdW90O1x1YmQwOVx1YzUyOCZxdW90O1x1Yzc1OCBcdWMwYWNcdWM3YTUgXHVjNWYwXHVjODg1XHVjNzc0XHViMjk0IFx1YzBhY1x1YzVjNVx1Yzc0NCBcdWJiZjhcdWFkNmRcdWM3M2NcdWI4NWMgXHVkNjU1XHVjN2E1XHVkNTU4XHVhZTMwXHViODVjIFx1YWNiMFx1YzgxNVx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViZDA5XHVjNTI4XHViMjk0IExBXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWQyMmNcdWM3OTBcdWM3OTBcdWI0ZTRcdWM3NDQgXHViOWNjXHViMDk4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWJiZjhcdWFkNmRcdWM3M2NcdWI4NWMgXHVjZDljXHViYzFjXHVkNTg4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YmU0NFx1ZDU4OVx1YWUzMFx1Yjk3YyBcdWIwYjRcdWI5YWNcdWFjZTAgXHViY2Y0XHViMmM4IFx1YWRmOFx1YWNmM1x1Yzc0MCBMQVx1YWMwMCBcdWM1NDRcdWIyYzhcdWM1YzhcdWIyZTQuIFx1YzVmMFx1Yzg4NVx1Yzc3NFx1Yzc1OCBcdWJlNDRcdWMxMWNcdWIyOTQgXHVjNTQ0XHViMjk0IFx1YmJmOFx1YWQ2ZCBcdWIzYzRcdWMyZGNcdWFjMDAgXHViMjc0XHVjNjk1XHViYzE2XHVjNWQwIFx1YzVjNlx1YzVjOFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YjJmOVx1YzVmMFx1ZDc4OCBcdWMwYWNcdWM3YTVcdWM3NTggXHVkNTZkXHVhY2Y1XHVkM2I4XHVjNzQ0IFx1YjI3NFx1YzY5NVx1ZDU4OVx1YzczY1x1Yjg1YyBcdWM2MDhcdWM1N2RcdWQ1NWMgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM1ZjBcdWM4ODVcdWM3NzRcdWIyOTQgTEFcdWFlNGNcdWM5YzAgXHVhYzAwXHViMjk0IFx1YmU0NFx1YzZhOVx1Yzc0NCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHVjOTA0XHVjNzc0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWFkZjhcdWIyOTQgXHViZTQ0XHVkNTg5XHVhZTMwXHViOTdjIFx1ZDBjMFx1YjI5NCBcdWIzMDBcdWMyZTBcdWM1ZDAgXHVjYzI4XHViOTdjIFx1YmU0Y1x1YjgyNFx1YzExYyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWJiZjhcdWFkNmRcdWM1ZDBcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWIzYzRcdWMyZGNcdWFjMDAgXHVjNzg4XHVhY2UwLCBcdWFjMDEgXHViM2M0XHVjMmRjXHViMjk0IDFcdWJjODhcdWJkODBcdWQxMzAgTlx1YmM4OFx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViNjEwLCBNXHVhYzFjXHVjNzU4IFx1YjNjNFx1Yjg1Y1x1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YjNjNFx1Yjg1Y1x1YjI5NCBcdWI0NTAgXHViM2M0XHVjMmRjXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YmE3MCwgXHVkNTVjIFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1Y1x1YjljYyBcdWM2YzBcdWM5YzFcdWM3N2MgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViMjc0XHVjNjk1XHVjNzU4IFx1YjNjNFx1YzJkYyBcdWJjODhcdWQ2MzhcdWIyOTQgMVx1YmM4OFx1Yzc3NFx1YWNlMCwgTEFcdWM3NTggXHViYzg4XHVkNjM4XHViMjk0IDJcdWJjODhcdWM3NzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzVmMFx1Yzg4NVx1Yzc3NFx1Yzc1OCBcdWQ2OGNcdWMwYWNcdWIyOTQgXHVhZDZjXHVhZTAwXHVjNzQ0IFx1YjExOFx1YjI5NCBcdWFjMDBcdWNlNThcdWI5N2MgXHVjOWMwXHViMmM4XHVhY2UwIFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzVmMFx1Yzg4NVx1Yzc3NFx1YWMwMCBcdWJjMjlcdWJiMzhcdWQ1NThcdWIyOTQgXHViM2M0XHVjMmRjXHVjNWQwIFx1YWNiZFx1ZDYzOFx1YzZkMFx1Yzc0NCBcdWFjZTBcdWM2YTlcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWFjZTBcdWM2YTlcdWQ1NzRcdWM1N2NcdWQ1NThcdWIyOTQgXHVhY2JkXHVkNjM4XHVjNmQwXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkNWNcdWMxOGNcdWQ2NTRcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjNWI0XHViNWE0IFx1YjNjNFx1YzJkY1x1YzVkMFx1YzExYyBcdWFjYmRcdWQ2MzhcdWM2ZDBcdWM3NDQgXHVhY2UwXHVjNmE5XHVkNTU4XHViYTc0LCBcdWJhODcgXHViYzg4XHVjNzQ0IFx1YmMyOVx1YmIzOFx1ZDU1OFx1YjM1NFx1Yjc3Y1x1YjNjNCBcdWM3YWNcdWFjZTBcdWM2YTlcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNTQ0XHViM2M0IFx1YjQxY1x1YjJlNC4gXHVjNWYwXHVjODg1XHVjNzc0XHViMjk0IFx1YjI3NFx1YzY5NVx1YzVkMFx1YzExYyBcdWNkOWNcdWJjMWNcdWQ1NzRcdWMxMWMgTEFcdWI5N2MgXHViYzI5XHViYjM4XHVkNTg4XHViMmU0XHVhYzAwIFx1YjJlNFx1YzJkYyBcdWIyNzRcdWM2OTVcdWM3M2NcdWI4NWMgXHViM2NjXHVjNTQ0XHVjNjI4XHViMmU0LjxcL3A+XHJcblxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgTlx1YWNmYyBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBOICZsZTsgMTAwLCAyICZsZTsgTSAmbGU7IDIwMCk8XC9wPlxyXG5cclxuPHA+XHJcblx0XHViMmU0XHVjNzRjIE1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjODE1XHVjMjE4IEFcdWM2NDAgQlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgQSwgQiAmbGU7IE4pIFx1Yzc3NCBcdWI0NTAgXHVjMjJiXHVjNzkwXHViMjk0IFx1YjNjNFx1Yjg1Y1x1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjODE1XHViY2Y0XHVjNzc0XHVhY2UwLCBBXHVjNWQwXHVjMTFjIEJcdWI4NWMgXHVhYzAwXHViMjk0IFx1YjNjNFx1Yjg1Y1x1Yjc3Y1x1YjI5NCBcdWI3M2JcdWM3NzRcdWIyZTQuIFx1YWMxOVx1Yzc0MCBcdWIzYzRcdWI4NWNcdWFjMDAgXHViNDUwIFx1YmM4OFx1Yzc3NFx1YzBjMSBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YzljMFx1YjljYywgXHViYzE4XHViMzAwIFx1YmMyOVx1ZDVhNSBcdWIzYzRcdWI4NWMoQiAtJmd0OyBBKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzggXHVjMjE4XHViMjk0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM3YWMgXHVjOTA0XHVjNWQwIFx1YjI3NFx1YzY5NVx1YzVkMFx1YzExYyBMQVx1Yjg1YyBcdWFjMTRcdWIyZTRcdWFjMDAsIFx1YjJlNFx1YzJkYyBcdWIyNzRcdWM2OTVcdWM3M2NcdWI4NWMgXHViM2NjXHVjNTQ0XHVjNjI0XHViMjk0IFx1YWNiZFx1Yjg1YyBcdWM5MTEgXHVhY2UwXHVjNmE5XHVkNTc0XHVjNTdjXHVkNTU4XHViMjk0IFx1YWNiZFx1ZDYzOFx1YzZkMFx1Yzc1OCBcdWMyMThcdWM3NTggXHVjZDVjXHVjMThjXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVkNTZkXHVjMGMxIFx1YjJmNVx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHViOWNjIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlxyXG5cdFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjNzc0XHViM2Q5XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC4gMS0mZ3Q7My0mZ3Q7NC0mZ3Q7Mi0mZ3Q7Ni0mZ3Q7My0mZ3Q7NC0mZ3Q7NS0mZ3Q7MTxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjc5NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IktBTVBBTkpBIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgZWxlY3Rpb25zIGFyZSBuZWFyaW5nLCBzbyBQcmVzaWRlbnQgQW1hYm8gS2NhcmFiIGlzIHBsYW5uaW5nIGEgdG91ciBvZiB0aGUgU3RhdGVzLCB3aXRoIHNwZWVjaGVzIGluIFdEQyBhbmQgTEEuIFRvIHByb3ZpZGUgYWRlcXVhdGUgc2VjdXJpdHksIHRoZSBTZWNyZXQgU2VydmljZSBuZWVkcyB0byBjb25zdGFudGx5IG1vbml0b3IgYWxsIGNpdGllcyB0aGF0IHRoZSBQcmVzaWRlbnQgd2lsbCBwYXNzIHRocm91Z2ggKGluY2x1ZGluZyBXREMgYW5kIExBKS48XC9wPlxyXG5cclxuPHA+T2YgY291cnNlLCB0aGUgZmVkZXJhbCBidWRnZXQgbmVlZHMgdG8gYmUgc3BlbnQgcmVzcG9uc2libHksIHNvIHRoZSBQcmVzaWRlbnQgd2lsbCBub3QgYmUgdXNpbmcgQUYxLCBidXQgd2lsbCBiZSB0cmF2ZWxsaW5nIGJ5IGNhci4gQWxzbywgdGhlIFNlY3JldCBTZXJ2aWNlIHdpbGwgcGxhbiB0aGUgUHJlc2lkZW50JiMzOTtzIHRvdXIgZnJvbSBXREMgdG8gTEEgYW5kIGJhY2sgdG8gV0RDIHN1Y2ggdGhhdCB0aGUgbGVhc3QgcG9zc2libGUgbnVtYmVyIG9mIGNpdGllcyBuZWVkcyB0byBiZSBtb25pdG9yZWQuPFwvcD5cclxuXHJcbjxwPkZvciB0aGlzIHByb2JsZW0sIGFzc3VtZSB0aGF0IHRoZSBTdGF0ZXMgY29uc2lzdCBvZiBOIGNpdGllcywgZGVub3RlZCBieSBudW1iZXJzIGZyb20gMSB0byBOLCBhbmQgTSB1bmlkaXJlY3Rpb25hbCBJbnRlcnN0YXRlcywgd2l0aCBlYWNoIEludGVyc3RhdGUgbGlua2luZyB0d28gZGlmZmVyZW50IGNpdGllcy4gV0RDIGlzIGNpdHkgbnVtYmVyIDEsIExBIG51bWJlciAyLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdG8gY29tcHV0ZSB0aGUgbWluaW11bSBudW1iZXIgb2YgY2l0aWVzIHRoYXQgbmVlZCB0byBiZSBtb25pdG9yZWQgc3VjaCB0aGF0IHRoZXJlIGV4aXN0cyBhIHBhdGggZnJvbSBXREMgdG8gTEEgYW5kIGJhY2sgdG8gV0RDIHBhc3Npbmcgb25seSB0aHJvdWdoIG1vbml0b3JlZCBjaXRpZXMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgdHdvIGludGVnZXJzIE4gYW5kIE0gKDIgJmxlOyBOICZsZTsgMTAwLCAyICZsZTsgTSAmbGU7IDIwMCksIHRoZSBudW1iZXIgb2YgY2l0aWVzIGFuZCB0aGUgbnVtYmVyIG9mIEludGVyc3RhdGVzIGxpbmtpbmcgdGhlIGNpdGllcywgcmVzcGVjdGl2ZWx5LjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTSBsaW5lcyBjb250YWlucyB0d28gZGlmZmVyZW50IGludGVnZXJzIEEsIEIgKDEgJmxlOyBBLCBCICZsZTsgTiksIHRoZSBiZWdpbm5pbmcgYW5kIGVuZGluZyBjaXR5IHNlcnZlZCBieSB0aGUgZ2l2ZW4gSW50ZXJzdGF0ZS4gTm8gdHdvIEludGVyc3RhdGVzIGxpbmsgdGhlIHNhbWUgdHdvIGNpdGllcyBpbiB0aGUgc2FtZSBkaXJlY3Rpb24sIGJ1dCB0d28gSW50ZXJzdGF0ZXMgY2FuIGxpbmsgdGhlIHNhbWUgdHdvIGNpdGllcyBpbiBvcHBvc2l0ZSBkaXJlY3Rpb25zLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIG1pbmltdW0gbnVtYmVyIG9mIGNpdGllcyB0aGF0IG5lZWQgdG8gYmUgbW9uaXRvcmVkLjxcL3A+XHJcblxyXG48cD5Ob3RlOiBUZXN0IGRhdGEgd2lsbCBlbnN1cmUgdGhhdCBhIHNvbHV0aW9uIHdpbGwgYWx3YXlzIGV4aXN0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5UaGUgUHJlc2lkZW50IGNhbiB0YWtlIHRoZSBmb2xsb3dpbmcgcm91dGU6IDEgLSZndDsgMyAtJmd0OyA0IC0mZ3Q7IDIgLSZndDsgNiAtJmd0OyAzIC0mZ3Q7IDQgLSZndDsgNSAtJmd0OyAxLiBTaW5jZSBoZSBuZWVkcyB0byBwYXNzIHRocm91Z2ggZWFjaCBjaXR5IGF0IGxlYXN0IG9uY2UsIHRoZSBzb2x1dGlvbiBpcyA2LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d