시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 288 61 41 29.496%

문제

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

봉씨는 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+XHJcblx0XHViMjc0XHVjNjk1XHVjNzU4IFx1YjNjNFx1YzJkYyBcdWJjODhcdWQ2MzhcdWIyOTQgMVx1YmM4OFx1Yzc3NFx1YWNlMCwgTEFcdWM3NTggXHViYzg4XHVkNjM4XHViMjk0IDJcdWJjODhcdWM3NzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzVmMFx1Yzg4NVx1Yzc3NFx1Yzc1OCBcdWQ2OGNcdWMwYWNcdWIyOTQgXHVhZDZjXHVhZTAwXHVjNzQ0IFx1YjExOFx1YjI5NCBcdWFjMDBcdWNlNThcdWI5N2MgXHVjOWMwXHViMmM4XHVhY2UwIFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzVmMFx1Yzg4NVx1Yzc3NFx1YWMwMCBcdWJjMjlcdWJiMzhcdWQ1NThcdWIyOTQgXHViM2M0XHVjMmRjXHVjNWQwIFx1YWNiZFx1ZDYzOFx1YzZkMFx1Yzc0NCBcdWFjZTBcdWM2YTlcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YWNlMFx1YzZhOVx1ZDU3NFx1YzU3Y1x1ZDU1OFx1YjI5NCBcdWFjYmRcdWQ2MzhcdWM2ZDBcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q1Y1x1YzE4Y1x1ZDY1NFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWM1YjRcdWI1YTQgXHViM2M0XHVjMmRjXHVjNWQwXHVjMTFjIFx1YWNiZFx1ZDYzOFx1YzZkMFx1Yzc0NCBcdWFjZTBcdWM2YTlcdWQ1NThcdWJhNzQsIFx1YmE4NyBcdWJjODhcdWM3NDQgXHViYzI5XHViYjM4XHVkNTU4XHViMzU0XHViNzdjXHViM2M0IFx1YzdhY1x1YWNlMFx1YzZhOVx1ZDU1OFx1YzljMCBcdWM1NGFcdWM1NDRcdWIzYzQgXHViNDFjXHViMmU0LiBcdWM1ZjBcdWM4ODVcdWM3NzRcdWIyOTQgXHViMjc0XHVjNjk1XHVjNWQwXHVjMTFjIFx1Y2Q5Y1x1YmMxY1x1ZDU3NFx1YzExYyBMQVx1Yjk3YyBcdWJjMjlcdWJiMzhcdWQ1ODhcdWIyZTRcdWFjMDAgXHViMmU0XHVjMmRjIFx1YjI3NFx1YzY5NVx1YzczY1x1Yjg1YyBcdWIzY2NcdWM1NDRcdWM2MjhcdWIyZTQuPFwvcD5cclxuXHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBOXHVhY2ZjIE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IE4gJmxlOyAxMDAsIDIgJmxlOyBNICZsZTsgMjAwKTxcL3A+XHJcblxyXG48cD5cclxuXHRcdWIyZTRcdWM3NGMgTVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWM4MTVcdWMyMTggQVx1YzY0MCBCXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBBLCBCICZsZTsgTikgXHVjNzc0IFx1YjQ1MCBcdWMyMmJcdWM3OTBcdWIyOTQgXHViM2M0XHViODVjXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM4MTVcdWJjZjRcdWM3NzRcdWFjZTAsIEFcdWM1ZDBcdWMxMWMgQlx1Yjg1YyBcdWFjMDBcdWIyOTQgXHViM2M0XHViODVjXHViNzdjXHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC4gXHVhYzE5XHVjNzQwIFx1YjNjNFx1Yjg1Y1x1YWMwMCBcdWI0NTAgXHViYzg4XHVjNzc0XHVjMGMxIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHVjOWMwXHViOWNjLCBcdWJjMThcdWIzMDAgXHViYzI5XHVkNWE1IFx1YjNjNFx1Yjg1YyhCIC0mZ3Q7IEEpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljOCBcdWMyMThcdWIyOTQgXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViMjc0XHVjNjk1XHVjNWQwXHVjMTFjIExBXHViODVjIFx1YWMxNFx1YjJlNFx1YWMwMCwgXHViMmU0XHVjMmRjIFx1YjI3NFx1YzY5NVx1YzczY1x1Yjg1YyBcdWIzY2NcdWM1NDRcdWM2MjRcdWIyOTQgXHVhY2JkXHViODVjIFx1YzkxMSBcdWFjZTBcdWM2YTlcdWQ1NzRcdWM1N2NcdWQ1NThcdWIyOTQgXHVhY2JkXHVkNjM4XHVjNmQwXHVjNzU4IFx1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWQ1NmRcdWMwYzEgXHViMmY1XHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWI5Y2MgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHJcblx0XHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWM3NzRcdWIzZDlcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LiAxLSZndDszLSZndDs0LSZndDsyLSZndDs2LSZndDszLSZndDs0LSZndDs1LSZndDsxPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI3OTUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJLQU1QQU5KQSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIGVsZWN0aW9ucyBhcmUgbmVhcmluZywgc28gUHJlc2lkZW50IEFtYWJvIEtjYXJhYiBpcyBwbGFubmluZyBhIHRvdXIgb2YgdGhlIFN0YXRlcywgd2l0aCBzcGVlY2hlcyBpbiBXREMgYW5kIExBLiBUbyBwcm92aWRlIGFkZXF1YXRlIHNlY3VyaXR5LCB0aGUgU2VjcmV0IFNlcnZpY2UgbmVlZHMgdG8gY29uc3RhbnRseSBtb25pdG9yIGFsbCBjaXRpZXMgdGhhdCB0aGUgUHJlc2lkZW50IHdpbGwgcGFzcyB0aHJvdWdoIChpbmNsdWRpbmcgV0RDIGFuZCBMQSkuPFwvcD5cclxuXHJcbjxwPk9mIGNvdXJzZSwgdGhlIGZlZGVyYWwgYnVkZ2V0IG5lZWRzIHRvIGJlIHNwZW50IHJlc3BvbnNpYmx5LCBzbyB0aGUgUHJlc2lkZW50IHdpbGwgbm90IGJlIHVzaW5nIEFGMSwgYnV0IHdpbGwgYmUgdHJhdmVsbGluZyBieSBjYXIuIEFsc28sIHRoZSBTZWNyZXQgU2VydmljZSB3aWxsIHBsYW4gdGhlIFByZXNpZGVudCYjMzk7cyB0b3VyIGZyb20gV0RDIHRvIExBIGFuZCBiYWNrIHRvIFdEQyBzdWNoIHRoYXQgdGhlIGxlYXN0IHBvc3NpYmxlIG51bWJlciBvZiBjaXRpZXMgbmVlZHMgdG8gYmUgbW9uaXRvcmVkLjxcL3A+XHJcblxyXG48cD5Gb3IgdGhpcyBwcm9ibGVtLCBhc3N1bWUgdGhhdCB0aGUgU3RhdGVzIGNvbnNpc3Qgb2YgTiBjaXRpZXMsIGRlbm90ZWQgYnkgbnVtYmVycyBmcm9tIDEgdG8gTiwgYW5kIE0gdW5pZGlyZWN0aW9uYWwgSW50ZXJzdGF0ZXMsIHdpdGggZWFjaCBJbnRlcnN0YXRlIGxpbmtpbmcgdHdvIGRpZmZlcmVudCBjaXRpZXMuIFdEQyBpcyBjaXR5IG51bWJlciAxLCBMQSBudW1iZXIgMi48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRvIGNvbXB1dGUgdGhlIG1pbmltdW0gbnVtYmVyIG9mIGNpdGllcyB0aGF0IG5lZWQgdG8gYmUgbW9uaXRvcmVkIHN1Y2ggdGhhdCB0aGVyZSBleGlzdHMgYSBwYXRoIGZyb20gV0RDIHRvIExBIGFuZCBiYWNrIHRvIFdEQyBwYXNzaW5nIG9ubHkgdGhyb3VnaCBtb25pdG9yZWQgY2l0aWVzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIHR3byBpbnRlZ2VycyBOIGFuZCBNICgyICZsZTsgTiAmbGU7IDEwMCwgMiAmbGU7IE0gJmxlOyAyMDApLCB0aGUgbnVtYmVyIG9mIGNpdGllcyBhbmQgdGhlIG51bWJlciBvZiBJbnRlcnN0YXRlcyBsaW5raW5nIHRoZSBjaXRpZXMsIHJlc3BlY3RpdmVseS48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE0gbGluZXMgY29udGFpbnMgdHdvIGRpZmZlcmVudCBpbnRlZ2VycyBBLCBCICgxICZsZTsgQSwgQiAmbGU7IE4pLCB0aGUgYmVnaW5uaW5nIGFuZCBlbmRpbmcgY2l0eSBzZXJ2ZWQgYnkgdGhlIGdpdmVuIEludGVyc3RhdGUuIE5vIHR3byBJbnRlcnN0YXRlcyBsaW5rIHRoZSBzYW1lIHR3byBjaXRpZXMgaW4gdGhlIHNhbWUgZGlyZWN0aW9uLCBidXQgdHdvIEludGVyc3RhdGVzIGNhbiBsaW5rIHRoZSBzYW1lIHR3byBjaXRpZXMgaW4gb3Bwb3NpdGUgZGlyZWN0aW9ucy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSBtaW5pbXVtIG51bWJlciBvZiBjaXRpZXMgdGhhdCBuZWVkIHRvIGJlIG1vbml0b3JlZC48XC9wPlxyXG5cclxuPHA+Tm90ZTogVGVzdCBkYXRhIHdpbGwgZW5zdXJlIHRoYXQgYSBzb2x1dGlvbiB3aWxsIGFsd2F5cyBleGlzdC48XC9wPlxyXG4iLCJoaW50IjoiPHA+VGhlIFByZXNpZGVudCBjYW4gdGFrZSB0aGUgZm9sbG93aW5nIHJvdXRlOiAxIC0mZ3Q7IDMgLSZndDsgNCAtJmd0OyAyIC0mZ3Q7IDYgLSZndDsgMyAtJmd0OyA0IC0mZ3Q7IDUgLSZndDsgMS4gU2luY2UgaGUgbmVlZHMgdG8gcGFzcyB0aHJvdWdoIGVhY2ggY2l0eSBhdCBsZWFzdCBvbmNlLCB0aGUgc29sdXRpb24gaXMgNi48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d