시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 27 5 5 33.333%

문제

서울 내의 고속도로 도로망의 이용 요금이 빠르게 증가하고 있다. 때문에 최적의 경로를 찾는 것이 실제 문제로 제기되고 있다. 고속도로 도로망은 두 도시간의 양방향 도로들로 구성되어 있다. 각각의 도로에 대해 도로 이용요금과 도로를 지나가는데 걸리는 시간이 알려져 있다.

경로는 여행하는데 이용하는 도로들을 나열한 것을 의미한다. 경로상의 총 이용시간은 이동하는 도로들의 이용요금의 총합을 말한다. 또한 경로상의 총 요금은 경로상의 도로들을 지나가는데 걸리는 시간의 합을 의미한다. 그리고 경로상의 총 이용시간이 적을수록, 이용요금이 적을수록 더 좋은 경로가 된다. 즉, 어떤 경로가 다른 경로보다 좋다는 말은 이 경로가 다른 경로보다 빠르고 이용요금이 적다는 것을 의미한다. 우리는 어떠한 경로가 다른 어떤 경로보다도 좋은 경로일 때 이를 최적의 경로라 부른다. 하지만 항상 이러한 최적의 경로가 존재하는 것은 아니다.

예를 들어, 아래의 그림과 같은 고속도로 도로망이 있다고 하자. 각각의 도로는 요금과 이동하는데 걸리는 시간을 나타내는 한 쌍의 숫자로 구성되어진다,

그리고 도시 1에서 도시 4로 가는데는 총 4가지 경로가 존재한다. 4가지 경로에 대해 총 이동시간과 요금을 계산하여 보면 1-2-4(요금 4, 시간 5), 1-3-4(요금 4, 시간 5), 1-2-3-4(요금 6, 시간 4), 1-3-2-4(요금 4, 비용 10)이 된다.

그리고 여기서 경로 1-3-4와 1-2-4가 경로 1-3-2-4보다 좋은 것을 알 수 있다. 이 도로망에서는 효율적인 요금-시간 쌍이 두 가지 존재한다. 요금 4, 시간 5(경로 1-2-4, 1-3-4), 요금 6, 시간 4(경로 1-2-3-4). 만약 요금을 많이 내더라도 빠른 길을 원한다면 경로 1-2-3-4를 선택하면 되고 반대로 시간은 조금 더 걸리더라도 요금을 적게 내고 싶으면 경로 1-3-4 또는 1-2-4를 선택하면 된다.

문제는 고속도로 도로망에 대한 정보가 주어지면 시작 도시에서 끝 도시까지 연결하는 효율적인 경로를 계산하는 것이다. 우리는 단지 서로 다른 효율적인 비용-시간 쌍의 개수만 출력하면 된다.

문제는 지역들이 노드로 구성된 그래프가 주어졌을 때 원샘이 원하는 지역 간의 거리를 신속히 알려주는 것이다.

입력

첫째 줄에 도시의 개수 n(1≤n≤100), 도로의 개수 m(1≤m≤300), 시작 도시 s, 도착 도시 e가 주어진다. (1≤s,e≤n, s≠e) 그 다음부터 m개의 줄에 도로에 대한 정보가 주어지는데 한 줄에 한 도로의 양 끝점 p, r(1≤p,r≤n, p≠r)과 요금 c(0≤c≤100), 그리고 시간 t(0≤t≤100)이 주어진다. 두 개 도시 사이에는 한 개 이상의 도로가 존재할 수 있다.

출력

첫 줄에 서로 다른 효율적인 비용-시간 쌍의 개수를 출력한다.

예제 입력 1

4 5 1 4
2 1 2 1
3 4 3 1
2 3 1 2
3 1 1 4
2 4 2 4

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjE3MDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzExY1x1YzZiOCBcdWIwYjRcdWM3NTggXHVhY2UwXHVjMThkXHViM2M0XHViODVjIFx1YjNjNFx1Yjg1Y1x1YjlkZFx1Yzc1OCBcdWM3NzRcdWM2YTkgXHVjNjk0XHVhZTA4XHVjNzc0IFx1YmU2MFx1Yjk3NFx1YWM4YyBcdWM5OWRcdWFjMDBcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjZDVjXHVjODAxXHVjNzU4IFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWNjM2VcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YzJlNFx1YzgxYyBcdWJiMzhcdWM4MWNcdWI4NWMgXHVjODFjXHVhZTMwXHViNDE4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVhY2UwXHVjMThkXHViM2M0XHViODVjIFx1YjNjNFx1Yjg1Y1x1YjlkZFx1Yzc0MCBcdWI0NTAgXHViM2M0XHVjMmRjXHVhYzA0XHVjNzU4IFx1YzU5MVx1YmMyOVx1ZDVhNSBcdWIzYzRcdWI4NWNcdWI0ZTRcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YjNjNFx1Yjg1Y1x1YzVkMCBcdWIzMDBcdWQ1NzQgXHViM2M0XHViODVjIFx1Yzc3NFx1YzZhOVx1YzY5NFx1YWUwOFx1YWNmYyBcdWIzYzRcdWI4NWNcdWI5N2MgXHVjOWMwXHViMDk4XHVhYzAwXHViMjk0XHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NzQgXHVjNTRjXHViODI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhY2JkXHViODVjXHViMjk0IFx1YzVlY1x1ZDU4OVx1ZDU1OFx1YjI5NFx1YjM3MCBcdWM3NzRcdWM2YTlcdWQ1NThcdWIyOTQgXHViM2M0XHViODVjXHViNGU0XHVjNzQ0IFx1YjA5OFx1YzVmNFx1ZDU1YyBcdWFjODNcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBcdWFjYmRcdWI4NWNcdWMwYzFcdWM3NTggXHVjZDFkIFx1Yzc3NFx1YzZhOVx1YzJkY1x1YWMwNFx1Yzc0MCBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTQgXHViM2M0XHViODVjXHViNGU0XHVjNzU4IFx1Yzc3NFx1YzZhOVx1YzY5NFx1YWUwOFx1Yzc1OCBcdWNkMWRcdWQ1NjlcdWM3NDQgXHViOWQwXHVkNTVjXHViMmU0LiBcdWI2MTBcdWQ1NWMgXHVhY2JkXHViODVjXHVjMGMxXHVjNzU4IFx1Y2QxZCBcdWM2OTRcdWFlMDhcdWM3NDAgXHVhY2JkXHViODVjXHVjMGMxXHVjNzU4IFx1YjNjNFx1Yjg1Y1x1YjRlNFx1Yzc0NCBcdWM5YzBcdWIwOThcdWFjMDBcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHVhY2JkXHViODVjXHVjMGMxXHVjNzU4IFx1Y2QxZCBcdWM3NzRcdWM2YTlcdWMyZGNcdWFjMDRcdWM3NzQgXHVjODAxXHVjNzQ0XHVjMjE4XHViODVkLCBcdWM3NzRcdWM2YTlcdWM2OTRcdWFlMDhcdWM3NzQgXHVjODAxXHVjNzQ0XHVjMjE4XHViODVkIFx1YjM1NCBcdWM4OGJcdWM3NDAgXHVhY2JkXHViODVjXHVhYzAwIFx1YjQxY1x1YjJlNC4gXHVjOTg5LCBcdWM1YjRcdWI1YTQgXHVhY2JkXHViODVjXHVhYzAwIFx1YjJlNFx1Yjk3OCBcdWFjYmRcdWI4NWNcdWJjZjRcdWIyZTQgXHVjODhiXHViMmU0XHViMjk0IFx1YjlkMFx1Yzc0MCBcdWM3NzQgXHVhY2JkXHViODVjXHVhYzAwIFx1YjJlNFx1Yjk3OCBcdWFjYmRcdWI4NWNcdWJjZjRcdWIyZTQgXHViZTYwXHViOTc0XHVhY2UwIFx1Yzc3NFx1YzZhOVx1YzY5NFx1YWUwOFx1Yzc3NCBcdWM4MDFcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gXHVjNmIwXHViOWFjXHViMjk0IFx1YzViNFx1YjVhMFx1ZDU1YyBcdWFjYmRcdWI4NWNcdWFjMDAgXHViMmU0XHViOTc4IFx1YzViNFx1YjVhNCBcdWFjYmRcdWI4NWNcdWJjZjRcdWIyZTRcdWIzYzQgXHVjODhiXHVjNzQwIFx1YWNiZFx1Yjg1Y1x1Yzc3YyBcdWI1NGMgXHVjNzc0XHViOTdjIFx1Y2Q1Y1x1YzgwMVx1Yzc1OCBcdWFjYmRcdWI4NWNcdWI3N2MgXHViZDgwXHViOTc4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MgXHVkNTZkXHVjMGMxIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWNkNWNcdWM4MDFcdWM3NTggXHVhY2JkXHViODVjXHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NDAgXHVjNTQ0XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWM1NDRcdWI3OThcdWM3NTggXHVhZGY4XHViOWJjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWMgXHViM2M0XHViODVjXHViOWRkXHVjNzc0IFx1Yzc4OFx1YjJlNFx1YWNlMCBcdWQ1NThcdWM3OTAuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWIzYzRcdWI4NWNcdWIyOTQgXHVjNjk0XHVhZTA4XHVhY2ZjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWQ1NWMgXHVjMzBkXHVjNzU4IFx1YzIyYlx1Yzc5MFx1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MThcdWM1YjRcdWM5YzRcdWIyZTQsPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMDVcL2dyYWdyYS5QTkdcIiBzdHlsZT1cImhlaWdodDoxNDNweDsgd2lkdGg6Mjc2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVhZGY4XHViOWFjXHVhY2UwIFx1YjNjNFx1YzJkYyAxXHVjNWQwXHVjMTFjIFx1YjNjNFx1YzJkYyA0XHViODVjIFx1YWMwMFx1YjI5NFx1YjM3MFx1YjI5NCBcdWNkMWQgNFx1YWMwMFx1YzljMCBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LiA0XHVhYzAwXHVjOWMwIFx1YWNiZFx1Yjg1Y1x1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjZDFkIFx1Yzc3NFx1YjNkOVx1YzJkY1x1YWMwNFx1YWNmYyBcdWM2OTRcdWFlMDhcdWM3NDQgXHVhY2M0XHVjMGIwXHVkNTU4XHVjNWVjIFx1YmNmNFx1YmE3NCAxLTItNChcdWM2OTRcdWFlMDggNCwgXHVjMmRjXHVhYzA0IDUpLCAxLTMtNChcdWM2OTRcdWFlMDggNCwgXHVjMmRjXHVhYzA0IDUpLCAxLTItMy00KFx1YzY5NFx1YWUwOCA2LCBcdWMyZGNcdWFjMDQgNCksIDEtMy0yLTQoXHVjNjk0XHVhZTA4IDQsIFx1YmU0NFx1YzZhOSAxMClcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjhcdWI5YWNcdWFjZTAgXHVjNWVjXHVhZTMwXHVjMTFjIFx1YWNiZFx1Yjg1YyAxLTMtNFx1YzY0MCAxLTItNFx1YWMwMCBcdWFjYmRcdWI4NWMgMS0zLTItNFx1YmNmNFx1YjJlNCBcdWM4OGJcdWM3NDAgXHVhYzgzXHVjNzQ0IFx1YzU0YyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzQgXHViM2M0XHViODVjXHViOWRkXHVjNWQwXHVjMTFjXHViMjk0IFx1ZDZhOFx1YzcyOFx1YzgwMVx1Yzc3OCBcdWM2OTRcdWFlMDgtXHVjMmRjXHVhYzA0IFx1YzMwZFx1Yzc3NCBcdWI0NTAgXHVhYzAwXHVjOWMwIFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC4gXHVjNjk0XHVhZTA4IDQsIFx1YzJkY1x1YWMwNCA1KFx1YWNiZFx1Yjg1YyAxLTItNCwgMS0zLTQpLCBcdWM2OTRcdWFlMDggNiwgXHVjMmRjXHVhYzA0IDQoXHVhY2JkXHViODVjIDEtMi0zLTQpLiBcdWI5Y2NcdWM1N2QgXHVjNjk0XHVhZTA4XHVjNzQ0IFx1YjljZVx1Yzc3NCBcdWIwYjRcdWIzNTRcdWI3N2NcdWIzYzQgXHViZTYwXHViOTc4IFx1YWUzOFx1Yzc0NCBcdWM2ZDBcdWQ1NWNcdWIyZTRcdWJhNzQgXHVhY2JkXHViODVjIDEtMi0zLTRcdWI5N2MgXHVjMTIwXHVkMGRkXHVkNTU4XHViYTc0IFx1YjQxOFx1YWNlMCBcdWJjMThcdWIzMDBcdWI4NWMgXHVjMmRjXHVhYzA0XHVjNzQwIFx1Yzg3MFx1YWUwOCBcdWIzNTQgXHVhYzc4XHViOWFjXHViMzU0XHViNzdjXHViM2M0IFx1YzY5NFx1YWUwOFx1Yzc0NCBcdWM4MDFcdWFjOGMgXHViMGI0XHVhY2UwIFx1YzJmNlx1YzczY1x1YmE3NCBcdWFjYmRcdWI4NWMgMS0zLTQgXHViNjEwXHViMjk0IDEtMi00XHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmIzOFx1YzgxY1x1YjI5NCBcdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWMgXHViM2M0XHViODVjXHViOWRkXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTc0IFx1YzJkY1x1Yzc5MSBcdWIzYzRcdWMyZGNcdWM1ZDBcdWMxMWMgXHViMDVkIFx1YjNjNFx1YzJkY1x1YWU0Y1x1YzljMCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVkNmE4XHVjNzI4XHVjODAxXHVjNzc4IFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM2YjBcdWI5YWNcdWIyOTQgXHViMmU4XHVjOWMwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVkNmE4XHVjNzI4XHVjODAxXHVjNzc4IFx1YmU0NFx1YzZhOS1cdWMyZGNcdWFjMDQgXHVjMzBkXHVjNzU4IFx1YWMxY1x1YzIxOFx1YjljYyBcdWNkOWNcdWI4MjVcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiMzhcdWM4MWNcdWIyOTQgXHVjOWMwXHVjNWVkXHViNGU0XHVjNzc0IFx1YjE3OFx1YjRkY1x1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MWMgXHVhZGY4XHViNzk4XHVkNTA0XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMgXHVjNmQwXHVjMGQ4XHVjNzc0IFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWM5YzBcdWM1ZWQgXHVhYzA0XHVjNzU4IFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWMyZTBcdWMxOGRcdWQ3ODggXHVjNTRjXHViODI0XHVjOGZjXHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViM2M0XHVjMmRjXHVjNzU4IFx1YWMxY1x1YzIxOCBuKDEmbGU7biZsZTsxMDApLCBcdWIzYzRcdWI4NWNcdWM3NTggXHVhYzFjXHVjMjE4IG0oMSZsZTttJmxlOzMwMCksIFx1YzJkY1x1Yzc5MSBcdWIzYzRcdWMyZGMgcywgXHViM2M0XHVjYzI5IFx1YjNjNFx1YzJkYyBlXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEmbGU7cyxlJmxlO24sIHMmbmU7ZSkgXHVhZGY4IFx1YjJlNFx1Yzc0Y1x1YmQ4MFx1ZDEzMCBtXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWIzYzRcdWI4NWNcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTRcdWIzNzAgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NWMgXHViM2M0XHViODVjXHVjNzU4IFx1YzU5MSBcdWIwNWRcdWM4MTAgcCwgcigxJmxlO3AsciZsZTtuLCBwJm5lO3IpXHVhY2ZjIFx1YzY5NFx1YWUwOCBjKDAmbGU7YyZsZTsxMDApLCBcdWFkZjhcdWI5YWNcdWFjZTAgXHVjMmRjXHVhYzA0IHQoMCZsZTt0JmxlOzEwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NTAgXHVhYzFjIFx1YjNjNFx1YzJkYyBcdWMwYWNcdWM3NzRcdWM1ZDBcdWIyOTQgXHVkNTVjIFx1YWMxYyBcdWM3NzRcdWMwYzFcdWM3NTggXHViM2M0XHViODVjXHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWQ2YThcdWM3MjhcdWM4MDFcdWM3NzggXHViZTQ0XHVjNmE5LVx1YzJkY1x1YWMwNCBcdWMzMGRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNzAyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQmljcml0ZXJpYWwgcm91dGluZyIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIG5ldHdvcmsgb2YgcGF5IGhpZ2h3YXlzIGluIEJ5dGVsYW5kIGlzIGdyb3dpbmcgdXAgdmVyeSByYXBpZGx5LiBJdCBoYXMgYmVjb21lIHNvIGRlbnNlLCB0aGF0IHRoZSBjaG9pY2Ugb2YgdGhlIGJlc3Qgcm91dGUgaXMgYSByZWFsIHByb2JsZW0uIFRoZSBuZXR3b3JrIG9mIGhpZ2h3YXlzIGNvbnNpc3RzIG9mIGJpZGlyZWN0aW9uYWwgcm9hZHMgY29ubmVjdGluZyBjaXRpZXMuIEVhY2ggc3VjaCByb2FkIGlzIGNoYXJhY3Rlcml6ZWQgYnkgdGhlIHRyYXZlbGluZyB0aW1lIGFuZCB0aGUgdG9sbCB0byBiZSBwYWlkLjxcL3A+XHJcblxyXG48cD5UaGUgcm91dGUgaXMgY29tcG9zZWQgb2YgY29uc2VjdXRpdmUgcm9hZHMgdG8gYmUgdHJhdmVsZWQuIFRoZSB0b3RhbCB0aW1lIG5lZWRlZCB0byB0cmF2ZWwgdGhlIHJvdXRlIGlzIGVxdWFsIHRvIHRoZSBzdW0gb2YgdHJhdmVsaW5nIHRpbWVzIG9mIHRoZSByb2FkcyBjb25zdGl0dXRpbmcgdGhlIHJvdXRlLiBUaGUgdG90YWwgZmVlIGZvciB0aGUgcm91dGUgaXMgZXF1YWwgdG8gdGhlIHN1bSBvZiB0b2xscyBmb3IgdGhlIHJvYWRzIG9mIHdoaWNoIHRoZSByb3V0ZSBjb25zaXN0cy4gVGhlIGZhc3RlciBvbmUgY2FuIHRyYXZlbCB0aGUgcm91dGUgYW5kIHRoZSBsb3dlciB0aGUgZmVlLCB0aGUgYmV0dGVyIHRoZSByb3V0ZS4gU3RyaWN0bHkgc3BlYWtpbmcsIG9uZSByb3V0ZSBpcyBiZXR0ZXIgdGhhbiB0aGUgb3RoZXIgaWYgb25lIGNhbiB0cmF2ZWwgaXQgZmFzdGVyIGFuZCBkb2VzIG5vdCBoYXZlIHRvIHBheSBtb3JlLCBvciB2aWNlIHZlcnNhOiBvbmUgY2FuIHBheSBsZXNzIGFuZCBjYW4gdHJhdmVsIGl0IG5vdCBzbG93ZXIgdGhhbiB0aGUgb3RoZXIgb25lLiBXZSB3aWxsIGNhbGwgYSByb3V0ZSBjb25uZWN0aW5nIHR3byBjaXRpZXMgbWluaW1hbCBpZiB0aGVyZSBpcyBubyBiZXR0ZXIgcm91dGUgY29ubmVjdGluZyB0aGVzZSBjaXRpZXMuIFVuZm9ydHVuYXRlbHksIG5vdCBhbHdheXMgZXhpc3RzIG9uZSBtaW5pbWFsIHJvdXRlICZuZGFzaDsgdGhlcmUgY2FuIGJlIHNldmVyYWwgaW5jb21wYXJhYmxlIHJvdXRlcyBvciB0aGVyZSBjYW4gYmUgbm8gcm91dGUgYXQgYWxsLjxcL3A+XHJcblxyXG48cD5UaGUgcGljdHVyZSBiZWxvdyBwcmVzZW50cyBhbiBleGFtcGxlIG5ldHdvcmsgb2YgaGlnaHdheXMuIEVhY2ggcm9hZCBpcyBhY2NvbXBhbmllZCBieSBhIHBhaXIgb2YgbnVtYmVyczogdGhlIHRvbGwgYW5kIHRoZSB0cmF2ZWxpbmcgdGltZS48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9oaWdoLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIzMnB4OyB3aWR0aDo0ODlweFwiIFwvPjxcL3A+XHJcblxyXG48cD5MZXQgdXMgY29uc2lkZXIgZm91ciBkaWZmZXJlbnQgcm91dGVzIGZyb20gY2l0eSAxIHRvIGNpdHkgNCwgdG9nZXRoZXIgd2l0aCB0aGVpciBmZWVzIGFuZCB0cmF2ZWxpbmcgdGltZXM6IDEgMiA0IChmZWUgNCwgdGltZSA1KSwgMSAzIDQgKGZlZSA0LCB0aW1lIDUpLCAxIDIgMyA0IChmZWUgNiwgdGltZSA0KSBhbmQgMSAzIDIgNCAoZmVlIDQsIHRpbWUgMTApLjxcL3A+XHJcblxyXG48cD5Sb3V0ZXMgMSAzIDQgYW5kIDEgMiA0IGFyZSBiZXR0ZXIgdGhhbiAxIDMgMiA0LiBUaGVyZSBhcmUgdHdvIG1pbmltYWwgcGFpcnMgZmVlIHRpbWU6IGZlZSA0LCB0aW1lIDUgKHJvb3RzIDEgMiA0IGFuZCAxIDMgNCkgYW5kIGZlZSA2LCB0aW1lIDQgKHJvb3QgMSAyIDMgNCkuIFdoZW4gY2hvb3NpbmcgdGhlIHJvdXRlIHdlIGhhdmUgdG8gZGVjaWRlIHdoZXRoZXIgd2UgcHJlZmVyIHRvIHRyYXZlbCBmYXN0ZXIgYnV0IHdlIG11c3QgcGF5IG1vcmUgKHJvdXRlIDEgMiAzIDQpLCBvciB3ZSB3b3VsZCByYXRoZXIgdHJhdmVsIHNsb3dlciBidXQgY2hlYXBlciAocm91dGUgMSAzIDQgb3IgMSAyIDQpLjxcL3A+XHJcblxyXG48cD5Zb3VyIHRhc2sgaXMgdG8gd3JpdGUgYSBwcm9ncmFtLCB3aGljaDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5SZWFkcyB0aGUgZGVzY3JpcHRpb24gb2YgdGhlIGhpZ2h3YXkgbmV0d29yayBhbmQgc3RhcnRpbmcgYW5kIGVuZGluZyBjaXRpZXMgb2YgdGhlIHJvdXRlIGZvcm0gdGhlIHRleHQgZmlsZSBiaWMuaW4uPFwvbGk+XHJcblx0PGxpPkNvbXB1dGVzIHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IG1pbmltYWwgcm91dGVzIGNvbm5lY3RpbmcgdGhlIHN0YXJ0aW5nIGFuZCBlbmRpbmcgY2l0eSwgaG93ZXZlciBhbGwgdGhlIHJvdXRlcyBjaGFyYWN0ZXJpemVkIGJ5IHRoZSBzYW1lIGZlZSBhbmQgdHJhdmVsaW5nIHRpbWUgY291bnQgYXMganVzdCBvbmUgcm91dGU7IHdlIGFyZSBpbnRlcmVzdGVkIGp1c3QgaW4gdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgbWluaW1hbCBwYWlycyBmZWUgdGltZS48XC9saT5cclxuXHQ8bGk+V3JpdGVzIHRoZSByZXN1bHQgdG8gdGhlIG91dHB1dCBmaWxlIGJpYy5vdXQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlRoZXJlIGFyZSBmb3VyIGludGVnZXJzLCBzZXBhcmF0ZWQgYnkgc2luZ2xlIHNwYWNlcywgaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIHRleHQgZmlsZSBiaWMuaW46IG51bWJlciBvZiBjaXRpZXMgbiAodGhleSBhcmUgbnVtYmVyZWQgZnJvbSAxIHRvIG4pLCAxICZsZTsgbiAmbGU7IDEwMCwgbnVtYmVyIG9mIHJvYWRzIG0sIDAgJmxlOyBtICZsZTsgMzAwLCBzdGFydGluZyBjaXR5IHMgYW5kIGVuZGluZyBjaXR5IGUgb2YgdGhlIHJvdXRlLCAxICZsZTsgcywgZSAmbGU7IG4sIHMgJm5lOyBlLiBUaGUgY29uc2VjdXRpdmUgbSBsaW5lcyBkZXNjcmliZSB0aGUgcm9hZHMsIG9uZSByb2FkIHBlciBsaW5lLiBFYWNoIG9mIHRoZXNlIGxpbmVzIGNvbnRhaW5zIGZvdXIgaW50ZWdlcnMgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXM6IHR3byBlbmRzIG9mIGEgcm9hZCBwIGFuZCByLCAxICZsZTsgcCwgciAmbGU7IG4sIHAgJm5lOyByLCB0aGUgdG9sbCBjLCAwICZsZTsgYyAmbGU7IDEwMCwgYW5kIHRoZSB0cmF2ZWxpbmcgdGltZSB0LCAwICZsZTsgdCAmbGU7IDEwMC4gVHdvIGNpdGllcyBjYW4gYmUgY29ubmVjdGVkIGJ5IG1vcmUgdGhhbiBvbmUgcm9hZC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gc2hvdWxkIHdyaXRlIG9uZSBpbnRlZ2VyLCBudW1iZXIgb2YgZGlmZmVyZW50IG1pbmltYWwgcGFpcnMgZmVlIHRpbWUgZm9yIHJvdXRlcyBmcm9tIHMgdG8gZSwgaW4gdGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2YgdGhlIHRleHQgZmlsZSBiaWMub3V0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2002 4번

  • 문제를 번역한 사람: author6
  • 문제의 오타를 찾은 사람: koosaga