시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 224 45 28 25.688%

문제

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

봉씨는 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+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzdhYyBcdWM5MDRcdWM1ZDAgXHViMjc0XHVjNjk1XHVjNWQwXHVjMTFjIExBXHViODVjIFx1YWMxNFx1YjJlNFx1YWMwMCwgXHViMmU0XHVjMmRjIFx1YjI3NFx1YzY5NVx1YzczY1x1Yjg1YyBcdWIzY2NcdWM1NDRcdWM2MjRcdWIyOTQgXHVhY2JkXHViODVjIFx1YzkxMSBcdWFjZTBcdWM2YTlcdWQ1NzRcdWM1N2NcdWQ1NThcdWIyOTQgXHVhY2JkXHVkNjM4XHVjNmQwXHVjNzU4IFx1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWQ1NmRcdWMwYzEgXHViMmY1XHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWI5Y2MgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHJcblx0XHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWM3NzRcdWIzZDlcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LiAxLSZndDszLSZndDs0LSZndDsyLSZndDs2LSZndDszLSZndDs0LSZndDs1LSZndDsxPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyNzk1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiS0FNUEFOSkEiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBlbGVjdGlvbnMgYXJlIG5lYXJpbmcsIHNvIFByZXNpZGVudCBBbWFibyBLY2FyYWIgaXMgcGxhbm5pbmcgYSB0b3VyIG9mIHRoZSBTdGF0ZXMsIHdpdGggc3BlZWNoZXMgaW4gV0RDIGFuZCBMQS4gVG8gcHJvdmlkZSBhZGVxdWF0ZSBzZWN1cml0eSwgdGhlIFNlY3JldCBTZXJ2aWNlIG5lZWRzIHRvIGNvbnN0YW50bHkgbW9uaXRvciBhbGwgY2l0aWVzIHRoYXQgdGhlIFByZXNpZGVudCB3aWxsIHBhc3MgdGhyb3VnaCAoaW5jbHVkaW5nIFdEQyBhbmQgTEEpLjxcL3A+XHJcblxyXG48cD5PZiBjb3Vyc2UsIHRoZSBmZWRlcmFsIGJ1ZGdldCBuZWVkcyB0byBiZSBzcGVudCByZXNwb25zaWJseSwgc28gdGhlIFByZXNpZGVudCB3aWxsIG5vdCBiZSB1c2luZyBBRjEsIGJ1dCB3aWxsIGJlIHRyYXZlbGxpbmcgYnkgY2FyLiBBbHNvLCB0aGUgU2VjcmV0IFNlcnZpY2Ugd2lsbCBwbGFuIHRoZSBQcmVzaWRlbnQmIzM5O3MgdG91ciBmcm9tIFdEQyB0byBMQSBhbmQgYmFjayB0byBXREMgc3VjaCB0aGF0IHRoZSBsZWFzdCBwb3NzaWJsZSBudW1iZXIgb2YgY2l0aWVzIG5lZWRzIHRvIGJlIG1vbml0b3JlZC48XC9wPlxyXG5cclxuPHA+Rm9yIHRoaXMgcHJvYmxlbSwgYXNzdW1lIHRoYXQgdGhlIFN0YXRlcyBjb25zaXN0IG9mIE4gY2l0aWVzLCBkZW5vdGVkIGJ5IG51bWJlcnMgZnJvbSAxIHRvIE4sIGFuZCBNIHVuaWRpcmVjdGlvbmFsIEludGVyc3RhdGVzLCB3aXRoIGVhY2ggSW50ZXJzdGF0ZSBsaW5raW5nIHR3byBkaWZmZXJlbnQgY2l0aWVzLiBXREMgaXMgY2l0eSBudW1iZXIgMSwgTEEgbnVtYmVyIDIuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0byBjb21wdXRlIHRoZSBtaW5pbXVtIG51bWJlciBvZiBjaXRpZXMgdGhhdCBuZWVkIHRvIGJlIG1vbml0b3JlZCBzdWNoIHRoYXQgdGhlcmUgZXhpc3RzIGEgcGF0aCBmcm9tIFdEQyB0byBMQSBhbmQgYmFjayB0byBXREMgcGFzc2luZyBvbmx5IHRocm91Z2ggbW9uaXRvcmVkIGNpdGllcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSB0d28gaW50ZWdlcnMgTiBhbmQgTSAoMiAmbGU7IE4gJmxlOyAxMDAsIDIgJmxlOyBNICZsZTsgMjAwKSwgdGhlIG51bWJlciBvZiBjaXRpZXMgYW5kIHRoZSBudW1iZXIgb2YgSW50ZXJzdGF0ZXMgbGlua2luZyB0aGUgY2l0aWVzLCByZXNwZWN0aXZlbHkuPFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBNIGxpbmVzIGNvbnRhaW5zIHR3byBkaWZmZXJlbnQgaW50ZWdlcnMgQSwgQiAoMSAmbGU7IEEsIEIgJmxlOyBOKSwgdGhlIGJlZ2lubmluZyBhbmQgZW5kaW5nIGNpdHkgc2VydmVkIGJ5IHRoZSBnaXZlbiBJbnRlcnN0YXRlLiBObyB0d28gSW50ZXJzdGF0ZXMgbGluayB0aGUgc2FtZSB0d28gY2l0aWVzIGluIHRoZSBzYW1lIGRpcmVjdGlvbiwgYnV0IHR3byBJbnRlcnN0YXRlcyBjYW4gbGluayB0aGUgc2FtZSB0d28gY2l0aWVzIGluIG9wcG9zaXRlIGRpcmVjdGlvbnMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgbWluaW11bSBudW1iZXIgb2YgY2l0aWVzIHRoYXQgbmVlZCB0byBiZSBtb25pdG9yZWQuPFwvcD5cclxuXHJcbjxwPk5vdGU6IFRlc3QgZGF0YSB3aWxsIGVuc3VyZSB0aGF0IGEgc29sdXRpb24gd2lsbCBhbHdheXMgZXhpc3QuPFwvcD5cclxuIiwiaGludCI6IjxwPlRoZSBQcmVzaWRlbnQgY2FuIHRha2UgdGhlIGZvbGxvd2luZyByb3V0ZTogMSAtJmd0OyAzIC0mZ3Q7IDQgLSZndDsgMiAtJmd0OyA2IC0mZ3Q7IDMgLSZndDsgNCAtJmd0OyA1IC0mZ3Q7IDEuIFNpbmNlIGhlIG5lZWRzIHRvIHBhc3MgdGhyb3VnaCBlYWNoIGNpdHkgYXQgbGVhc3Qgb25jZSwgdGhlIHNvbHV0aW9uIGlzIDYuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=