시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 512 MB127564543.689%

문제

세종이는 행성이 n개 있는 태양계의 왕이다. 행성 수가 너무 많아서 이름을 일일이 붙이는 것은 포기한 지 오래고, 대신 1~n의 구분되는 번호로 표기한다. 세종이의 집은 1번 행성에, PC방은 2번 행성에 위치한다. 또한 세종이는 고대부터 그 누구보다도 빠르게 PC방으로 달려가 핫타임을 놓치지 않기 위해 1번, 2번 행성을 왕래하게 해 주는 전용 비밀 양방향 텔레포터를 마련하고 있었으며, 한 번 이동하는 데 250분이 걸린다.

시대가 발전하여 각 행성들 사이에 교통을 위한 텔레포터가 많이 생겼다. 각각의 텔레포터는 양방향이고 이동에 정확히 한 시간이 걸린다. 행성의 시민들은 행성경제 활성화를 위하여 더 많은 텔레포터를 설치해줄 것을 세종이에게 부탁하였다.

세종이는 성군이 되기 위해 최대한 많은 부탁을 들어주려고 하지만, 단 한 가지는 용납할 수 없다. 텔레포터가 추가로 설치되다가 1번, 2번 행성 사이의 이동 시간이 자신의 비밀 텔레포터를 사용한 것, 즉 250분보다 빨라지는 것이다. 그러면 세종이가 핫타임 이벤트에 참가하기 위해 PC방 자리를 잡는 것에 차질이 생길지도 모른다.

따라서 세종이는 1번, 2번 행성을 교통 텔레포터들을 사용해 왕래하는 데 항상 250분보다 많은 시간이 들게 하면서 태양계에 최대한 많은 텔레포터를 설치하고 싶다. 몇 개의 텔레포터를 설치할 수 있을까? 물론 동일한 행성 쌍 사이에 여러 개의 텔레포터를 설치하는 건 무의미하기 때문에 그런 행동은 피할 것이다. 세종이가 그런 무의미한 곳에 비용을 들일 바에 차라리 자기 캐릭터에 현질을 하는 게 이득이다.

입력

첫째 줄에 행성 수 n과 이미 설치된 교통 텔레포터 수 m이 주어진다. (2 ≤ n ≤ 40,000, 0 ≤ m ≤ 1,000,000)

둘째 줄부터 m개의 줄에 걸쳐 기존의 각 텔레포터가 연결한 서로 다른 두 행성의 번호가 주어진다. 각 번호는 1 이상 n 이하의 정수이다. 여기엔 세종이의 전용 텔레포터는 포함되어 있지 않다. 같은 곳을 연결하는 텔레포터가 2번 이상 등장하지 않는다.

기존에 연결된 텔레포터만을 가지고는 어떠한 경로를 거치더라도 1번 행성과 2번 행성 사이를 250분 미만의 시간으로 왕래할 수 없음이 보장된다. 물론 그 이상이 시간으로 왕래가 가능할 수는 있다.

출력

첫째 줄에 추가로 건설할 수 있는 텔레포터 개수의 최댓값을 출력한다.

예제 입력 1

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

예제 출력 1

10

힌트

예제를 그림으로 나타낸 것이다. 실선이 이미 연결된 텔레포터이며 점선이 최대한 더 지을 수 있는 텔레포터들을 나타낸 것이다.

W3sicHJvYmxlbV9pZCI6IjgxOTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQwYjlcdWMxMzhcdWM4ODUiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzEzOFx1Yzg4NVx1Yzc3NFx1YjI5NCBcdWQ1ODlcdWMxMzFcdWM3NzQgblx1YWMxYyBcdWM3ODhcdWIyOTQgXHVkMGRjXHVjNTkxXHVhY2M0XHVjNzU4IFx1YzY1NVx1Yzc3NFx1YjJlNC4gXHVkNTg5XHVjMTMxIFx1YzIxOFx1YWMwMCBcdWIxMDhcdWJiMzQgXHViOWNlXHVjNTQ0XHVjMTFjIFx1Yzc3NFx1Yjk4NFx1Yzc0NCBcdWM3N2NcdWM3N2NcdWM3NzQgXHViZDk5XHVjNzc0XHViMjk0IFx1YWM4M1x1Yzc0MCBcdWQzZWNcdWFlMzBcdWQ1NWMgXHVjOWMwIFx1YzYyNFx1Yjc5OFx1YWNlMCwgXHViMzAwXHVjMmUwIDF+blx1Yzc1OCBcdWFkNmNcdWJkODRcdWI0MThcdWIyOTQgXHViYzg4XHVkNjM4XHViODVjIFx1ZDQ1Y1x1YWUzMFx1ZDU1Y1x1YjJlNC4gXHVjMTM4XHVjODg1XHVjNzc0XHVjNzU4IFx1YzlkMVx1Yzc0MCAxXHViYzg4IFx1ZDU4OVx1YzEzMVx1YzVkMCwgUENcdWJjMjlcdWM3NDAgMlx1YmM4OCBcdWQ1ODlcdWMxMzFcdWM1ZDAgXHVjNzA0XHVjZTU4XHVkNTVjXHViMmU0LiBcdWI2MTBcdWQ1NWMgXHVjMTM4XHVjODg1XHVjNzc0XHViMjk0IFx1YWNlMFx1YjMwMFx1YmQ4MFx1ZDEzMCBcdWFkZjggXHViMjA0XHVhZDZjXHViY2Y0XHViMmU0XHViM2M0IFx1YmU2MFx1Yjk3NFx1YWM4YyBQQ1x1YmMyOVx1YzczY1x1Yjg1YyBcdWIyZWNcdWI4MjRcdWFjMDAgXHVkNTZiXHVkMGMwXHVjNzg0XHVjNzQ0IFx1YjE5M1x1Y2U1OFx1YzljMCBcdWM1NGFcdWFlMzAgXHVjNzA0XHVkNTc0IDFcdWJjODgsIDJcdWJjODggXHVkNTg5XHVjMTMxXHVjNzQ0IFx1YzY1NVx1Yjc5OFx1ZDU1OFx1YWM4YyBcdWQ1NzQgXHVjOGZjXHViMjk0IFx1YzgwNFx1YzZhOSBcdWJlNDRcdWJjMDAgXHVjNTkxXHViYzI5XHVkNWE1IFx1ZDE1NFx1YjgwOFx1ZDNlY1x1ZDEzMFx1Yjk3YyBcdWI5YzhcdWI4MjhcdWQ1NThcdWFjZTAgXHVjNzg4XHVjNWM4XHVjNzNjXHViYTcwLCBcdWQ1NWMgXHViYzg4IFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NCBcdWIzNzAgMjUwXHViZDg0XHVjNzc0IFx1YWM3OFx1YjliMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMmRjXHViMzAwXHVhYzAwIFx1YmMxY1x1YzgwNFx1ZDU1OFx1YzVlYyBcdWFjMDEgXHVkNTg5XHVjMTMxXHViNGU0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWFkNTBcdWQxYjVcdWM3NDQgXHVjNzA0XHVkNTVjIFx1ZDE1NFx1YjgwOFx1ZDNlY1x1ZDEzMFx1YWMwMCBcdWI5Y2VcdWM3NzQgXHVjMGRkXHVhY2JjXHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVkMTU0XHViODA4XHVkM2VjXHVkMTMwXHViMjk0IFx1YzU5MVx1YmMyOVx1ZDVhNVx1Yzc3NFx1YWNlMCBcdWM3NzRcdWIzZDlcdWM1ZDAgXHVjODE1XHVkNjU1XHVkNzg4IFx1ZDU1YyBcdWMyZGNcdWFjMDRcdWM3NzQgXHVhYzc4XHViOWIwXHViMmU0LiBcdWQ1ODlcdWMxMzFcdWM3NTggXHVjMmRjXHViYmZjXHViNGU0XHVjNzQwIFx1ZDU4OVx1YzEzMVx1YWNiZFx1YzgxYyBcdWQ2NWNcdWMxMzFcdWQ2NTRcdWI5N2MgXHVjNzA0XHVkNTU4XHVjNWVjIFx1YjM1NCBcdWI5Y2VcdWM3NDAgXHVkMTU0XHViODA4XHVkM2VjXHVkMTMwXHViOTdjIFx1YzEyNFx1Y2U1OFx1ZDU3NFx1YzkwNCBcdWFjODNcdWM3NDQgXHVjMTM4XHVjODg1XHVjNzc0XHVjNWQwXHVhYzhjIFx1YmQ4MFx1ZDBjMVx1ZDU1OFx1YzYwMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTM4XHVjODg1XHVjNzc0XHViMjk0IFx1YzEzMVx1YWQ3MFx1Yzc3NCBcdWI0MThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWI5Y2VcdWM3NDAgXHViZDgwXHVkMGMxXHVjNzQ0IFx1YjRlNFx1YzViNFx1YzhmY1x1YjgyNFx1YWNlMCBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YjJlOCBcdWQ1NWMgXHVhYzAwXHVjOWMwXHViMjk0IFx1YzZhOVx1YjBhOVx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LiBcdWQxNTRcdWI4MDhcdWQzZWNcdWQxMzBcdWFjMDAgXHVjZDk0XHVhYzAwXHViODVjIFx1YzEyNFx1Y2U1OFx1YjQxOFx1YjJlNFx1YWMwMCAxXHViYzg4LCAyXHViYzg4IFx1ZDU4OVx1YzEzMSBcdWMwYWNcdWM3NzRcdWM3NTggXHVjNzc0XHViM2Q5IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWM3OTBcdWMyZTBcdWM3NTggXHViZTQ0XHViYzAwIFx1ZDE1NFx1YjgwOFx1ZDNlY1x1ZDEzMFx1Yjk3YyBcdWMwYWNcdWM2YTlcdWQ1NWMgXHVhYzgzLCBcdWM5ODkgMjUwXHViZDg0XHViY2Y0XHViMmU0IFx1YmU2OFx1Yjc3Y1x1YzljMFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YWRmOFx1YjdlY1x1YmE3NCBcdWMxMzhcdWM4ODVcdWM3NzRcdWFjMDAgXHVkNTZiXHVkMGMwXHVjNzg0IFx1Yzc3NFx1YmNhNFx1ZDJiOFx1YzVkMCBcdWNjMzhcdWFjMDBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFBDXHViYzI5IFx1Yzc5MFx1YjlhY1x1Yjk3YyBcdWM3YTFcdWIyOTQgXHVhYzgzXHVjNWQwIFx1Y2MyOFx1YzljOFx1Yzc3NCBcdWMwZGRcdWFlMzhcdWM5YzBcdWIzYzQgXHViYWE4XHViOTc4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI1MzBcdWI3N2NcdWMxMWMgXHVjMTM4XHVjODg1XHVjNzc0XHViMjk0IDFcdWJjODgsIDJcdWJjODggXHVkNTg5XHVjMTMxXHVjNzQ0IFx1YWQ1MFx1ZDFiNSBcdWQxNTRcdWI4MDhcdWQzZWNcdWQxMzBcdWI0ZTRcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTc0IFx1YzY1NVx1Yjc5OFx1ZDU1OFx1YjI5NCBcdWIzNzAgXHVkNTZkXHVjMGMxIDI1MFx1YmQ4NFx1YmNmNFx1YjJlNCBcdWI5Y2VcdWM3NDAgXHVjMmRjXHVhYzA0XHVjNzc0IFx1YjRlNFx1YWM4YyBcdWQ1NThcdWJhNzRcdWMxMWMgXHVkMGRjXHVjNTkxXHVhY2M0XHVjNWQwIFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWI5Y2VcdWM3NDAgXHVkMTU0XHViODA4XHVkM2VjXHVkMTMwXHViOTdjIFx1YzEyNFx1Y2U1OFx1ZDU1OFx1YWNlMCBcdWMyZjZcdWIyZTQuIFx1YmE4NyBcdWFjMWNcdWM3NTggXHVkMTU0XHViODA4XHVkM2VjXHVkMTMwXHViOTdjIFx1YzEyNFx1Y2U1OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNzQ0XHVhZTRjPyBcdWJiM2NcdWI4NjAgXHViM2Q5XHVjNzdjXHVkNTVjIFx1ZDU4OVx1YzEzMSBcdWMzMGQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTU0XHViODA4XHVkM2VjXHVkMTMwXHViOTdjIFx1YzEyNFx1Y2U1OFx1ZDU1OFx1YjI5NCBcdWFjNzQgXHViYjM0XHVjNzU4XHViYmY4XHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWFkZjhcdWI3ZjAgXHVkNTg5XHViM2Q5XHVjNzQwIFx1ZDUzY1x1ZDU2MCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YzEzOFx1Yzg4NVx1Yzc3NFx1YWMwMCBcdWFkZjhcdWI3ZjAgXHViYjM0XHVjNzU4XHViYmY4XHVkNTVjIFx1YWNmM1x1YzVkMCBcdWJlNDRcdWM2YTlcdWM3NDQgXHViNGU0XHVjNzdjIFx1YmMxNFx1YzVkMCBcdWNjMjhcdWI3N2NcdWI5YWMgXHVjNzkwXHVhZTMwIFx1Y2U5MFx1YjlhZFx1ZDEzMFx1YzVkMCBcdWQ2MDRcdWM5YzhcdWM3NDQgXHVkNTU4XHViMjk0IFx1YWM4YyBcdWM3NzRcdWI0ZGRcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDU4OVx1YzEzMSBcdWMyMTggblx1YWNmYyBcdWM3NzRcdWJiZjggXHVjMTI0XHVjZTU4XHViNDFjIFx1YWQ1MFx1ZDFiNSBcdWQxNTRcdWI4MDhcdWQzZWNcdWQxMzAgXHVjMjE4IG1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IG4gJmxlOyA0MCwwMDAsIDAgJmxlOyBtICZsZTsgMSwwMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIG1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWFlMzBcdWM4NzRcdWM3NTggXHVhYzAxIFx1ZDE1NFx1YjgwOFx1ZDNlY1x1ZDEzMFx1YWMwMCBcdWM1ZjBcdWFjYjBcdWQ1NWMgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWI0NTAgXHVkNTg5XHVjMTMxXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWJjODhcdWQ2MzhcdWIyOTQgMSBcdWM3NzRcdWMwYzEgbiBcdWM3NzRcdWQ1NThcdWM3NTggXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LiBcdWM1ZWNcdWFlMzBcdWM1ZDQgXHVjMTM4XHVjODg1XHVjNzc0XHVjNzU4IFx1YzgwNFx1YzZhOSBcdWQxNTRcdWI4MDhcdWQzZWNcdWQxMzBcdWIyOTQgXHVkM2VjXHVkNTY4XHViNDE4XHVjNWI0IFx1Yzc4OFx1YzljMCBcdWM1NGFcdWIyZTQuIFx1YWMxOVx1Yzc0MCBcdWFjZjNcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1ZDE1NFx1YjgwOFx1ZDNlY1x1ZDEzMFx1YWMwMCAyXHViYzg4IFx1Yzc3NFx1YzBjMSBcdWI0ZjFcdWM3YTVcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFlMzBcdWM4NzRcdWM1ZDAgXHVjNWYwXHVhY2IwXHViNDFjIFx1ZDE1NFx1YjgwOFx1ZDNlY1x1ZDEzMFx1YjljY1x1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjZTBcdWIyOTQgXHVjNWI0XHViNWEwXHVkNTVjIFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWFjNzBcdWNlNThcdWIzNTRcdWI3N2NcdWIzYzQgMVx1YmM4OCBcdWQ1ODlcdWMxMzFcdWFjZmMgMlx1YmM4OCBcdWQ1ODlcdWMxMzEgXHVjMGFjXHVjNzc0XHViOTdjIDI1MFx1YmQ4NCBcdWJiZjhcdWI5Y2NcdWM3NTggXHVjMmRjXHVhYzA0XHVjNzNjXHViODVjIFx1YzY1NVx1Yjc5OFx1ZDU2MCBcdWMyMTggXHVjNWM2XHVjNzRjXHVjNzc0IFx1YmNmNFx1YzdhNVx1YjQxY1x1YjJlNC4gXHViYjNjXHViODYwIFx1YWRmOCBcdWM3NzRcdWMwYzFcdWM3NzQgXHVjMmRjXHVhYzA0XHVjNzNjXHViODVjIFx1YzY1NVx1Yjc5OFx1YWMwMCBcdWFjMDBcdWIyYTVcdWQ1NjAgXHVjMjE4XHViMjk0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2Q5NFx1YWMwMFx1Yjg1YyBcdWFjNzRcdWMxMjRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWQxNTRcdWI4MDhcdWQzZWNcdWQxMzAgXHVhYzFjXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLWFwLW5vcnRoZWFzdC0xLmFtYXpvbmF3cy5jb21cL3Byb2JsZW1cLzgxOTNcLzEuZ2lmXCIgc3R5bGU9XCJoZWlnaHQ6MTY5cHg7IHdpZHRoOjE1N3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1YzgxY1x1Yjk3YyBcdWFkZjhcdWI5YmNcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI4IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVjMmU0XHVjMTIwXHVjNzc0IFx1Yzc3NFx1YmJmOCBcdWM1ZjBcdWFjYjBcdWI0MWMgXHVkMTU0XHViODA4XHVkM2VjXHVkMTMwXHVjNzc0XHViYTcwIFx1YzgxMFx1YzEyMFx1Yzc3NCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViMzU0IFx1YzljMFx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1ZDE1NFx1YjgwOFx1ZDNlY1x1ZDEzMFx1YjRlNFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjggXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiODE5MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRlbGVwb3J0YXRpb24iLCJkZXNjcmlwdGlvbiI6IjxwPktpbmcgQnl0ZWFzYXIgaXMgdGhlIHJ1bGVyIG9mIHRoZSB3aG9sZSBzb2xhciBzeXN0ZW0gdGhhdCBjb250YWlucyBuIHBsYW5ldHMuIFRoaXMgbnVtYmVyIGlzIHNvIGxhcmdlIHRoYXQgcGVvcGxlIGhhdmUgYWJhbmRvbmVkIHRoZSBzaWxseSBjdXN0b20gb2YgbmFtaW5nIHRoZSBwbGFuZXRzIGFuZCB1c2UgbnVtYmVycyBpbnN0ZWFkLiBUaGUgcGxhbmV0cyBhcmUgdGh1cyBjb252ZW5pZW50bHkgbnVtYmVyZWQgZnJvbSAxIHRvIG4uIEJ5dGVhc2FyJiMzOTtzIHBhbGFjZSBpcyBvbiB0aGUgcGxhbmV0IG5vLiAxLCB3aGlsZSBoaXMgbWlsaXRhcnkgYmFzZSBvbiB0aGUgcGxhbmV0IG5vLiAyLiBBIGxvbmcgdGltZSBhZ28gQnl0ZWFzYXIgaGFkIGEgdGVsZXBvcnRhdGlvbiBwb3J0YWwgZXN0YWJsaXNoZWQgYmV0d2VlbiB0aGVzZSB0d28gcGxhbmV0cywgd2hpY2ggYWxsb3dzIHRyYXZlbGxpbmcgZnJvbSBlaXRoZXIgcGxhbmV0IHRvIGFub3RoZXIgaW4gdHdvIGh1bmRyZWQgYW5kIGZpZnR5IG1pbnV0ZXMgKHNsaWdodGx5IG92ZXIgZm91ciBob3VycykuPFwvcD5cclxuXHJcbjxwPk5vd2FkYXlzIHRoZSB0ZWxlcG9ydGF0aW9uIHRlY2hub2xvZ3kgaXMgbW9yZSBtYXR1cmUsIGFuZCB0aGUgcmVjZW50IHRlbGVwb3J0YXRpb24gZGV2aWNlcyBzaG9ydGVuIHRoZSB0cmF2ZWwgdGltZSB0byBqdXN0IGEgc2luZ2xlIGhvdXIuIExldCB1cyBub3RlIGhlcmUsIHRoYXQgYWxsIHRoZSBwb3J0YWxzLCBib3RoIHRoZSBCeXRlYXNhciYjMzk7cyBvbGQgb25lIGFuZCB0aGUgbmV3IG9uZXMgYXZhaWxhYmxlIG9uIHRoZSBtYXJrZXQsIGFyZSBvZiBjb3Vyc2UgYmlkaXJlY3Rpb25hbCwgYW5kIHRoYXQgdGhlIHRlbGVwb3J0YXRpb24gdHJhdmVsIHRpbWUgaXMgaXJyZXNwZWN0aXZlIG9mIHRoZSBkaXN0YW5jZSB0cmF2ZWxsZWQuIFNvbWUgcGxhbmV0cyBvZiB0aGUgc3lzdGVtIGFyZSBhbHJlYWR5IGNvbm5lY3RlZCB3aXRoIHRoZXNlIG5ldyB0ZWxlcG9ydGF0aW9uIHBvcnRhbHMuIEluIGZhY3QsIGl0IGlzIGFscmVhZHkgcG9zc2libGUgdG8gdHJhdmVsIGJldHdlZW4gdGhlIHBsYW5ldHMgbm8uIDEgYW5kIDIgd2l0aG91dCB1c2luZyB0aGUga2luZyYjMzk7cyBwcml2YXRlIHBvcnRhbCwgdGhvdWdoIHRoaXMgaW52b2x2ZXMgc2V2ZXJhbCBvdGhlciBwb3J0YWxzIGFuZCBpcyB0aHVzIG5vIGZhc3RlciB0aGFuIHRoZSBraW5nJiMzOTtzIHBvcnRhbC4gQnl0ZWFzYXIgZmluZHMgdGhpcyByYXRoZXIgZm9ydHVuYXRlLCBhcyBoZSBiZWxpZXZlcyB0aGF0IHN1Y2ggcG9zc2liaWxpdHkgd291bGQgYmUgYSBzZWN1cml0eSBicmVhY2guPFwvcD5cclxuXHJcbjxwPlRoZSB0ZWNobm9sb2d5IGl0c2VsZiBpcyBpbmNyZWFzaW5nbHkgYXZhaWxhYmxlLCBhbmQgYXMgZXZlcnlvbmUgcmVhbGlzZXMgaXRzIGVjb25vbWljIHNpZ25pZmljYW5jZSwgZWFjaCBwYWlyIG9mIHBsYW5ldHMgdGhhdCBhcmUgbm90IGN1cnJlbnRseSBkaXJlY3RseSBjb25uZWN0ZWQgd2l0aCBhIHBvcnRhbCBhcmUgcGV0aXRpb25pbmcgZm9yIGVzdGFibGlzaGluZyBzdWNoIGEgY29ubmVjdGlvbi4gQmVpbmcgYSB3aXNlIHJ1bGVyLCBCeXRlYXNhciBpbnRlbmRzIHRvIGdpdmUgaGlzIGNvbnNlbnQgdG8gYXMgbWFueSBjb25zdHJ1Y3Rpb25zIGFzIHBvc3NpYmxlLCB0aG91Z2gga2VlcGluZyBoaW1zZWxmIHNlY3VyZSwgaS5lLiwgbm90IGFsbG93aW5nIHRoZSB0cmF2ZWwgYmV0d2VlbiBwbGFuZXRzIDEgYW5kIDIgZmFzdGVyIHRoYW4gd2l0aCBoaXMgcHJpdmF0ZSBwb3J0YWwuIEhlbHAgdGhlIGtpbmcgZGV0ZXJtaW5lIGhvdyBtYW55IHBvcnRhbHMgaGUgY2FuIGFncmVlIHRvLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VHdvIGludGVnZXJzIGFyZSBnaXZlbiBpbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgc3RhbmRhcmQgaW5wdXQsIG4gYW5kIG0gKDIgJmxlOyBuICZsZTsgNDAsMDAwLCAwICZsZTsgbSAmbGU7IDEsMDAwLDAwMCksIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZSwgZGVub3RpbmcgdGhlIG51bWJlciBvZiBwbGFuZXRzIGluIEJ5dGVhc2FyJiMzOTtzIHJlYWxtIGFuZCB0aGUgbnVtYmVyIG9mIG5ldyBwb3J0YWxzIHRoYXQgYWxyZWFkeSBleGlzdC4gVGhlc2UgdGVsZXBvcnRhdGlvbiBwb3J0YWxzIGFyZSBkZXNjcmliZWQgaW4gdGhlIG0gbGluZXMgdGhhdCBmb2xsb3cuIEVhY2ggc3VjaCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBhPHN1Yj5pPFwvc3ViPiBhbmQgYjxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBhPHN1Yj5pPFwvc3ViPiAmbHQ7IGI8c3ViPmk8XC9zdWI+ICZsZTsgbiksIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZSwgZGVub3RpbmcgdGhhdCB0aGVyZSBpcyBhIHRlbGVwb3J0YXRpb24gcG9ydGFsIG9mIHRoZSBuZXcga2luZCBjb25uZWN0aW5nIGFpIGFuZCBiaS4gTm8gcGFpciBvZiBudW1iZXJzIGFwcGVhcnMgdHdpY2UuIFlvdSBtYXkgYXNzdW1lIHRoYXQgdGhlIGV4aXN0aW5nIG5ldHdvcmsgb2YgbmV3IHBvcnRhbHMgYWxsb3dzIHRyYXZlbCBmcm9tIHBsYW5ldCBuby4gMSB0byBwbGFuZXQgbm8uIDIsIGJ1dCBpbiBubyBsZXNzIHRoYW4gMjUwIG1pbnV0ZXMuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBzaG91bGQgcHJpbnQgb3V0IGp1c3QgYSBzaW5nbGUgaW50ZWdlciwgbmFtZWx5IHRoZSBtYXhpbXVtIG51bWJlciBvZiBwb3J0YWxzIEJ5dGVhc2FyIGNhbiBhZ3JlZSB0byB3aXRob3V0IGJyZWFjaGluZyBoaXMgc2VjdXJpdHkuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC9wcm9ibGVtXC84MTkzXC8xLmdpZlwiIHN0eWxlPVwiaGVpZ2h0OjE2OXB4OyB3aWR0aDoxNTdweFwiIFwvPjxcL3A+XHJcblxyXG48cD5FeGlzdGluZyBwb3J0YWxzIGFyZSBtYXJrZWQgd2l0aCBzb2xpZCBsaW5lcywgd2hpbGUgdGhvc2UgQnl0ZWFzYXIgY2FuIGFncmVlIHRvIHdpdGggZGFzaGVkIGxpbmVzLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > Polish Olympiad in Informatics > POI 2009/2010 > Stage 2 5번

  • 문제를 번역한 사람: kks227