시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB320725130.723%

문제

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

봉씨는 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

예제 입력 2

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

예제 출력 2

6

힌트

첫 번째 예제의 경우 1 → 3 → 4 → 2 → 6 → 3 → 4 → 5 → 1와 같이 이동하면 된다.

W3sicHJvYmxlbV9pZCI6IjI3OTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYWNcdWM1YzUgXHVkNjU1XHVjN2E1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxMzFcdWFjZjVcdWQ1NWMgXHViY2E0XHVjY2QwXHVkNjhjXHVjMGFjICZxdW90O1x1YmQwOVx1YzUyOCZxdW90O1x1Yzc1OCBcdWMwYWNcdWM3YTUgXHVjNWYwXHVjODg1XHVjNzc0XHViMjk0IFx1YzBhY1x1YzVjNVx1Yzc0NCBcdWJiZjhcdWFkNmRcdWM3M2NcdWI4NWMgXHVkNjU1XHVjN2E1XHVkNTU4XHVhZTMwXHViODVjIFx1YWNiMFx1YzgxNVx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViZDA5XHVjNTI4XHViMjk0IExBXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWQyMmNcdWM3OTBcdWM3OTBcdWI0ZTRcdWM3NDQgXHViOWNjXHViMDk4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWJiZjhcdWFkNmRcdWM3M2NcdWI4NWMgXHVjZDljXHViYzFjXHVkNTg4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YmU0NFx1ZDU4OVx1YWUzMFx1Yjk3YyBcdWIwYjRcdWI5YWNcdWFjZTAgXHViY2Y0XHViMmM4IFx1YWRmOFx1YWNmM1x1Yzc0MCBMQVx1YWMwMCBcdWM1NDRcdWIyYzhcdWM1YzhcdWIyZTQuIFx1YzVmMFx1Yzg4NVx1Yzc3NFx1Yzc1OCBcdWJlNDRcdWMxMWNcdWIyOTQgXHVjNTQ0XHViMjk0IFx1YmJmOFx1YWQ2ZCBcdWIzYzRcdWMyZGNcdWFjMDAgXHViMjc0XHVjNjk1XHViYzE2XHVjNWQwIFx1YzVjNlx1YzVjOFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YjJmOVx1YzVmMFx1ZDc4OCBcdWMwYWNcdWM3YTVcdWM3NTggXHVkNTZkXHVhY2Y1XHVkM2I4XHVjNzQ0IFx1YjI3NFx1YzY5NVx1ZDU4OVx1YzczY1x1Yjg1YyBcdWM2MDhcdWM1N2RcdWQ1NWMgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1ZjBcdWM4ODVcdWM3NzRcdWIyOTQgTEFcdWFlNGNcdWM5YzAgXHVhYzAwXHViMjk0IFx1YmU0NFx1YzZhOVx1Yzc0NCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHVjOTA0XHVjNzc0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWFkZjhcdWIyOTQgXHViZTQ0XHVkNTg5XHVhZTMwXHViOTdjIFx1ZDBjMFx1YjI5NCBcdWIzMDBcdWMyZTBcdWM1ZDAgXHVjYzI4XHViOTdjIFx1YmU0Y1x1YjgyNFx1YzExYyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiZjhcdWFkNmRcdWM1ZDBcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWIzYzRcdWMyZGNcdWFjMDAgXHVjNzg4XHVhY2UwLCBcdWFjMDEgXHViM2M0XHVjMmRjXHViMjk0IDFcdWJjODhcdWJkODBcdWQxMzAgTlx1YmM4OFx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViNjEwLCBNXHVhYzFjXHVjNzU4IFx1YjNjNFx1Yjg1Y1x1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YjNjNFx1Yjg1Y1x1YjI5NCBcdWI0NTAgXHViM2M0XHVjMmRjXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YmE3MCwgXHVkNTVjIFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1Y1x1YjljYyBcdWM2YzBcdWM5YzFcdWM3N2MgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMjc0XHVjNjk1XHVjNzU4IFx1YjNjNFx1YzJkYyBcdWJjODhcdWQ2MzhcdWIyOTQgMVx1YmM4OFx1Yzc3NFx1YWNlMCwgTEFcdWM3NTggXHViYzg4XHVkNjM4XHViMjk0IDJcdWJjODhcdWM3NzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YzVmMFx1Yzg4NVx1Yzc3NFx1Yzc1OCBcdWQ2OGNcdWMwYWNcdWIyOTQgXHVhZDZjXHVhZTAwXHVjNzQ0IFx1YjExOFx1YjI5NCBcdWFjMDBcdWNlNThcdWI5N2MgXHVjOWMwXHViMmM4XHVhY2UwIFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzVmMFx1Yzg4NVx1Yzc3NFx1YWMwMCBcdWJjMjlcdWJiMzhcdWQ1NThcdWIyOTQgXHViM2M0XHVjMmRjXHVjNWQwIFx1YWNiZFx1ZDYzOFx1YzZkMFx1Yzc0NCBcdWFjZTBcdWM2YTlcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YWNlMFx1YzZhOVx1ZDU3NFx1YzU3Y1x1ZDU1OFx1YjI5NCBcdWFjYmRcdWQ2MzhcdWM2ZDBcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q1Y1x1YzE4Y1x1ZDY1NFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWM1YjRcdWI1YTQgXHViM2M0XHVjMmRjXHVjNWQwXHVjMTFjIFx1YWNiZFx1ZDYzOFx1YzZkMFx1Yzc0NCBcdWFjZTBcdWM2YTlcdWQ1NThcdWJhNzQsIFx1YmE4NyBcdWJjODhcdWM3NDQgXHViYzI5XHViYjM4XHVkNTU4XHViMzU0XHViNzdjXHViM2M0IFx1YzdhY1x1YWNlMFx1YzZhOVx1ZDU1OFx1YzljMCBcdWM1NGFcdWM1NDRcdWIzYzQgXHViNDFjXHViMmU0LiBcdWM1ZjBcdWM4ODVcdWM3NzRcdWIyOTQgXHViMjc0XHVjNjk1XHVjNWQwXHVjMTFjIFx1Y2Q5Y1x1YmMxY1x1ZDU3NFx1YzExYyBMQVx1Yjk3YyBcdWJjMjlcdWJiMzhcdWQ1ODhcdWIyZTRcdWFjMDAgXHViMmU0XHVjMmRjIFx1YjI3NFx1YzY5NVx1YzczY1x1Yjg1YyBcdWIzY2NcdWM1NDRcdWM2MjhcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IE5cdWFjZmMgTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgTiAmbGU7IDEwMCwgMiAmbGU7IE0gJmxlOyAyMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBNXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YzgxNVx1YzIxOCBBXHVjNjQwIEJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEEsIEIgJmxlOyBOKSBcdWM3NzQgXHViNDUwIFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWIzYzRcdWI4NWNcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzgxNVx1YmNmNFx1Yzc3NFx1YWNlMCwgQVx1YzVkMFx1YzExYyBCXHViODVjIFx1YWMwMFx1YjI5NCBcdWIzYzRcdWI4NWNcdWI3N2NcdWIyOTQgXHViNzNiXHVjNzc0XHViMmU0LiBcdWFjMTlcdWM3NDAgXHViM2M0XHViODVjXHVhYzAwIFx1YjQ1MCBcdWJjODhcdWM3NzRcdWMwYzEgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWM5YzBcdWI5Y2MsIFx1YmMxOFx1YjMwMCBcdWJjMjlcdWQ1YTUgXHViM2M0XHViODVjKEIgLSZndDsgQSlcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YzIxOFx1YjI5NCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIyNzRcdWM2OTVcdWM1ZDBcdWMxMWMgTEFcdWI4NWMgXHVhYzE0XHViMmU0XHVhYzAwLCBcdWIyZTRcdWMyZGMgXHViMjc0XHVjNjk1XHVjNzNjXHViODVjIFx1YjNjY1x1YzU0NFx1YzYyNFx1YjI5NCBcdWFjYmRcdWI4NWMgXHVjOTExIFx1YWNlMFx1YzZhOVx1ZDU3NFx1YzU3Y1x1ZDU1OFx1YjI5NCBcdWFjYmRcdWQ2MzhcdWM2ZDBcdWM3NTggXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1ZDU2ZFx1YzBjMSBcdWIyZjVcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjljYyBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzYwOFx1YzgxY1x1Yzc1OCBcdWFjYmRcdWM2YjAgMSAmcmFycjsgMyAmcmFycjsgNCAmcmFycjsgMiAmcmFycjsgNiAmcmFycjsgMyAmcmFycjsgNCAmcmFycjsgNSAmcmFycjsgMVx1YzY0MCBcdWFjMTlcdWM3NzQgXHVjNzc0XHViM2Q5XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI3OTUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJLQU1QQU5KQSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIGVsZWN0aW9ucyBhcmUgbmVhcmluZywgc28gUHJlc2lkZW50IEFtYWJvIEtjYXJhYiBpcyBwbGFubmluZyBhIHRvdXIgb2YgdGhlIFN0YXRlcywgd2l0aCBzcGVlY2hlcyBpbiBXREMgYW5kIExBLiBUbyBwcm92aWRlIGFkZXF1YXRlIHNlY3VyaXR5LCB0aGUgU2VjcmV0IFNlcnZpY2UgbmVlZHMgdG8gY29uc3RhbnRseSBtb25pdG9yIGFsbCBjaXRpZXMgdGhhdCB0aGUgUHJlc2lkZW50IHdpbGwgcGFzcyB0aHJvdWdoIChpbmNsdWRpbmcgV0RDIGFuZCBMQSkuPFwvcD5cclxuXHJcbjxwPk9mIGNvdXJzZSwgdGhlIGZlZGVyYWwgYnVkZ2V0IG5lZWRzIHRvIGJlIHNwZW50IHJlc3BvbnNpYmx5LCBzbyB0aGUgUHJlc2lkZW50IHdpbGwgbm90IGJlIHVzaW5nIEFGMSwgYnV0IHdpbGwgYmUgdHJhdmVsbGluZyBieSBjYXIuIEFsc28sIHRoZSBTZWNyZXQgU2VydmljZSB3aWxsIHBsYW4gdGhlIFByZXNpZGVudCYjMzk7cyB0b3VyIGZyb20gV0RDIHRvIExBIGFuZCBiYWNrIHRvIFdEQyBzdWNoIHRoYXQgdGhlIGxlYXN0IHBvc3NpYmxlIG51bWJlciBvZiBjaXRpZXMgbmVlZHMgdG8gYmUgbW9uaXRvcmVkLjxcL3A+XHJcblxyXG48cD5Gb3IgdGhpcyBwcm9ibGVtLCBhc3N1bWUgdGhhdCB0aGUgU3RhdGVzIGNvbnNpc3Qgb2YgTiBjaXRpZXMsIGRlbm90ZWQgYnkgbnVtYmVycyBmcm9tIDEgdG8gTiwgYW5kIE0gdW5pZGlyZWN0aW9uYWwgSW50ZXJzdGF0ZXMsIHdpdGggZWFjaCBJbnRlcnN0YXRlIGxpbmtpbmcgdHdvIGRpZmZlcmVudCBjaXRpZXMuIFdEQyBpcyBjaXR5IG51bWJlciAxLCBMQSBudW1iZXIgMi48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRvIGNvbXB1dGUgdGhlIG1pbmltdW0gbnVtYmVyIG9mIGNpdGllcyB0aGF0IG5lZWQgdG8gYmUgbW9uaXRvcmVkIHN1Y2ggdGhhdCB0aGVyZSBleGlzdHMgYSBwYXRoIGZyb20gV0RDIHRvIExBIGFuZCBiYWNrIHRvIFdEQyBwYXNzaW5nIG9ubHkgdGhyb3VnaCBtb25pdG9yZWQgY2l0aWVzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIHR3byBpbnRlZ2VycyBOIGFuZCBNICgyICZsZTsgTiAmbGU7IDEwMCwgMiAmbGU7IE0gJmxlOyAyMDApLCB0aGUgbnVtYmVyIG9mIGNpdGllcyBhbmQgdGhlIG51bWJlciBvZiBJbnRlcnN0YXRlcyBsaW5raW5nIHRoZSBjaXRpZXMsIHJlc3BlY3RpdmVseS48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE0gbGluZXMgY29udGFpbnMgdHdvIGRpZmZlcmVudCBpbnRlZ2VycyBBLCBCICgxICZsZTsgQSwgQiAmbGU7IE4pLCB0aGUgYmVnaW5uaW5nIGFuZCBlbmRpbmcgY2l0eSBzZXJ2ZWQgYnkgdGhlIGdpdmVuIEludGVyc3RhdGUuIE5vIHR3byBJbnRlcnN0YXRlcyBsaW5rIHRoZSBzYW1lIHR3byBjaXRpZXMgaW4gdGhlIHNhbWUgZGlyZWN0aW9uLCBidXQgdHdvIEludGVyc3RhdGVzIGNhbiBsaW5rIHRoZSBzYW1lIHR3byBjaXRpZXMgaW4gb3Bwb3NpdGUgZGlyZWN0aW9ucy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSBtaW5pbXVtIG51bWJlciBvZiBjaXRpZXMgdGhhdCBuZWVkIHRvIGJlIG1vbml0b3JlZC48XC9wPlxyXG5cclxuPHA+Tm90ZTogVGVzdCBkYXRhIHdpbGwgZW5zdXJlIHRoYXQgYSBzb2x1dGlvbiB3aWxsIGFsd2F5cyBleGlzdC48XC9wPlxyXG4iLCJoaW50IjoiPHA+Rmlyc3Qgc2FtcGxlIGRlc2NyaXB0aW9uOiBUaGUgUHJlc2lkZW50IGNhbiB0YWtlIHRoZSBmb2xsb3dpbmcgcm91dGU6IDEgJnJhcnI7IDMgJnJhcnI7IDQgJnJhcnI7IDIgJnJhcnI7IDYgJnJhcnI7IDMgJnJhcnI7IDQgJnJhcnI7IDUgJnJhcnI7IDEuIFNpbmNlIGhlIG5lZWRzIHRvIHBhc3MgdGhyb3VnaCBlYWNoIGNpdHkgYXQgbGVhc3Qgb25jZSwgdGhlIHNvbHV0aW9uIGlzIDYuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d