시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB88653321247037.918%

문제

농부 존은 남는 시간에 MooTube라 불리는 동영상 공유 서비스를 만들었다. MooTube에서 농부 존의 소들은 재밌는 동영상들을 서로 공유할 수 있다. 소들은 MooTube에 1부터 N까지 번호가 붙여진 N (1 ≤ N ≤ 5,000)개의 동영상을 이미 올려 놓았다. 하지만, 존은 아직 어떻게 하면 소들이 그들이 좋아할 만한 새 동영상을 찾을 수 있을지 괜찮은 방법을 떠올리지 못했다.

농부 존은 모든 MooTube 동영상에 대해 “연관 동영상” 리스트를 만들기로 했다. 이렇게 하면 소들은 지금 보고 있는 동영상과 연관성이 높은 동영상을 추천 받을 수 있을 것이다.

존은 두 동영상이 서로 얼마나 가까운 지를 측정하는 단위인 “USADO”를 만들었다. 존은 N-1개의 동영상 쌍을 골라서 직접 두 쌍의 USADO를 계산했다. 그 다음에 존은 이 동영상들을 네트워크 구조로 바꿔서, 각 동영상을 정점으로 나타내기로 했다. 또 존은 동영상들의 연결 구조를 서로 연결되어 있는 N-1개의 동영상 쌍으로 나타내었다. 좀 더 쉽게 말해서, 존은 N-1개의 동영상 쌍을 골라서 어떤 동영상에서 다른 동영상으로 가는 경로가 반드시 하나 존재하도록 했다. 존은 임의의 두 쌍 사이의 동영상의 USADO를 그 경로의 모든 연결들의 USADO 중 최솟값으로 하기로 했다.

존은 어떤 주어진 MooTube 동영상에 대해, 값 K를 정해서 그 동영상과 USADO가 K 이상인 모든 동영상이 추천되도록 할 것이다. 하지만 존은 너무 많은 동영상이 추천되면 소들이 일하는 것이 방해될까 봐 걱정하고 있다! 그래서 그는 K를 적절한 값으로 결정하려고 한다. 농부 존은 어떤 K 값에 대한 추천 동영상의 개수를 묻는 질문 여러 개에 당신이 대답해주기를 바란다.

입력

입력의 첫 번째 줄에는 N과 Q가 주어진다. (1 ≤ Q ≤ 5,000)

다음 N-1개의 줄에는 농부 존이 직접 잰 두 동영상 쌍의 USADO가 한 줄에 하나씩 주어진다. 각 줄은 세 정수 pi, qi, ri (1 ≤ pi, qi ≤ N, 1 ≤ ri ≤ 1,000,000,000)를 포함하는데, 이는 동영상 pi와 qi가 USADO ri로 서로 연결되어 있음을 뜻한다.

다음 Q개의 줄에는 농부 존의 Q개의 질문이 주어진다. 각 줄은 두 정수 ki와 vi(1 ≤ ki ≤ 1,000,000,000, 1 ≤ vi ≤ N)을 포함하는데, 이는 존의 i번째 질문이 만약 K = ki라면 동영상 vi를 보고 있는 소들에게 몇 개의 동영상이 추천될 지 묻는 것이라는 것을 뜻한다.

출력

Q개의 줄을 출력한다. i번째 줄에는 농부 존의 i번째 질문에 대한 답변이 출력되어야 한다.

예제 입력 1

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

예제 출력 1

3
0
2

힌트

농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 USADO는 min(3,2)=2가 되고, 1번 동영상과 4번 동영상의 USADO는 min(3,4)=3이 되고, 3번 동영상과 4번 동영상의 USADO는 min(2,4)=2가 된다.

농부 존은 K=1일 때 2번 동영상, K=3일 때 1번 동영상, K=4일 때 1번 동영상을 보면 각각 몇 개의 동영상이 추천될까 궁금해하고 있다. K=1일 때 2번 동영상에서 추천되는 동영상은 1, 3, 4번 동영상이다. K=4일 때 1번 동영상으로부터 추천되는 동영상은 없다. 그러나 K=3일때는 1번 동영상에서 2번 동영상과 4번 동영상이 추천된다.

W3sicHJvYmxlbV9pZCI6IjE1NTkxIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiTW9vVHViZSAoU2lsdmVyKSIsImRlc2NyaXB0aW9uIjoiPHA+XHViMThkXHViZDgwIFx1Yzg3NFx1Yzc0MCBcdWIwYThcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNWQwIE1vb1R1YmVcdWI3N2MgXHViZDg4XHViOWFjXHViMjk0IFx1YjNkOVx1YzYwMVx1YzBjMSBcdWFjZjVcdWM3MjAgXHVjMTFjXHViZTQ0XHVjMmE0XHViOTdjIFx1YjljY1x1YjRlNFx1YzVjOFx1YjJlNC4gTW9vVHViZVx1YzVkMFx1YzExYyBcdWIxOGRcdWJkODAgXHVjODc0XHVjNzU4IFx1YzE4Y1x1YjRlNFx1Yzc0MCBcdWM3YWNcdWJjMGNcdWIyOTQgXHViM2Q5XHVjNjAxXHVjMGMxXHViNGU0XHVjNzQ0IFx1YzExY1x1Yjg1YyBcdWFjZjVcdWM3MjBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjMThjXHViNGU0XHVjNzQwIE1vb1R1YmVcdWM1ZDAgMVx1YmQ4MFx1ZDEzMCBOXHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWJkOTlcdWM1ZWNcdWM5YzQgTiAoMSAmbGU7IE4gJmxlOyA1LDAwMClcdWFjMWNcdWM3NTggXHViM2Q5XHVjNjAxXHVjMGMxXHVjNzQ0IFx1Yzc3NFx1YmJmOCBcdWM2MmNcdWI4MjQgXHViMTkzXHVjNTU4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1Yzg3NFx1Yzc0MCBcdWM1NDRcdWM5YzEgXHVjNWI0XHViNWJiXHVhYzhjIFx1ZDU1OFx1YmE3NCBcdWMxOGNcdWI0ZTRcdWM3NzQgXHVhZGY4XHViNGU0XHVjNzc0IFx1Yzg4Ylx1YzU0NFx1ZDU2MCBcdWI5Y2NcdWQ1NWMgXHVjMGM4IFx1YjNkOVx1YzYwMVx1YzBjMVx1Yzc0NCBcdWNjM2VcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1Yzc0NFx1YzljMCBcdWFkMWNcdWNjMmVcdWM3NDAgXHViYzI5XHViYzk1XHVjNzQ0IFx1YjVhMFx1YzYyY1x1YjlhY1x1YzljMCBcdWJhYmJcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjE4ZFx1YmQ4MCBcdWM4NzRcdWM3NDAgXHViYWE4XHViNGUwIE1vb1R1YmUgXHViM2Q5XHVjNjAxXHVjMGMxXHVjNWQwIFx1YjMwMFx1ZDU3NCAmbGRxdW87XHVjNWYwXHVhZDAwIFx1YjNkOVx1YzYwMVx1YzBjMSZyZHF1bzsgXHViOWFjXHVjMmE0XHVkMmI4XHViOTdjIFx1YjljY1x1YjRlNFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuIFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWQ1NThcdWJhNzQgXHVjMThjXHViNGU0XHVjNzQwIFx1YzljMFx1YWUwOCBcdWJjZjRcdWFjZTAgXHVjNzg4XHViMjk0IFx1YjNkOVx1YzYwMVx1YzBjMVx1YWNmYyBcdWM1ZjBcdWFkMDBcdWMxMzFcdWM3NzQgXHViMTkyXHVjNzQwIFx1YjNkOVx1YzYwMVx1YzBjMVx1Yzc0NCBcdWNkOTRcdWNjOWMgXHViYzFiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWM3NDQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4NzRcdWM3NDAgXHViNDUwIFx1YjNkOVx1YzYwMVx1YzBjMVx1Yzc3NCBcdWMxMWNcdWI4NWMgXHVjNWJjXHViOWM4XHViMDk4IFx1YWMwMFx1YWU0Y1x1YzZiNCBcdWM5YzBcdWI5N2MgXHVjZTIxXHVjODE1XHVkNTU4XHViMjk0IFx1YjJlOFx1YzcwNFx1Yzc3OCAmbGRxdW87VVNBRE8mcmRxdW87XHViOTdjIFx1YjljY1x1YjRlNFx1YzVjOFx1YjJlNC4gXHVjODc0XHVjNzQwIE4tMVx1YWMxY1x1Yzc1OCBcdWIzZDlcdWM2MDFcdWMwYzEgXHVjMzBkXHVjNzQ0IFx1YWNlOFx1Yjc3Y1x1YzExYyBcdWM5YzFcdWM4MTEgXHViNDUwIFx1YzMwZFx1Yzc1OCBVU0FET1x1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1ODhcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGNcdWM1ZDAgXHVjODc0XHVjNzQwIFx1Yzc3NCBcdWIzZDlcdWM2MDFcdWMwYzFcdWI0ZTRcdWM3NDQgXHViMTI0XHVkMmI4XHVjNmNjXHVkMDZjIFx1YWQ2Y1x1Yzg3MFx1Yjg1YyBcdWJjMTRcdWFmZDRcdWMxMWMsIFx1YWMwMSBcdWIzZDlcdWM2MDFcdWMwYzFcdWM3NDQgXHVjODE1XHVjODEwXHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuIFx1YjYxMCBcdWM4NzRcdWM3NDAgXHViM2Q5XHVjNjAxXHVjMGMxXHViNGU0XHVjNzU4IFx1YzVmMFx1YWNiMCBcdWFkNmNcdWM4NzBcdWI5N2MgXHVjMTFjXHViODVjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgTi0xXHVhYzFjXHVjNzU4IFx1YjNkOVx1YzYwMVx1YzBjMSBcdWMzMGRcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI0XHVjNWM4XHViMmU0LiBcdWM4ODAgXHViMzU0IFx1YzI3ZFx1YWM4YyBcdWI5ZDBcdWQ1NzRcdWMxMWMsIFx1Yzg3NFx1Yzc0MCBOLTFcdWFjMWNcdWM3NTggXHViM2Q5XHVjNjAxXHVjMGMxIFx1YzMwZFx1Yzc0NCBcdWFjZThcdWI3N2NcdWMxMWMgXHVjNWI0XHViNWE0IFx1YjNkOVx1YzYwMVx1YzBjMVx1YzVkMFx1YzExYyBcdWIyZTRcdWI5NzggXHViM2Q5XHVjNjAxXHVjMGMxXHVjNzNjXHViODVjIFx1YWMwMFx1YjI5NCBcdWFjYmRcdWI4NWNcdWFjMDAgXHViYzE4XHViNGRjXHVjMmRjIFx1ZDU1OFx1YjA5OCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIzYzRcdWI4NWQgXHVkNTg4XHViMmU0LiBcdWM4NzRcdWM3NDAgXHVjNzg0XHVjNzU4XHVjNzU4IFx1YjQ1MCBcdWMzMGQgXHVjMGFjXHVjNzc0XHVjNzU4IFx1YjNkOVx1YzYwMVx1YzBjMVx1Yzc1OCBVU0FET1x1Yjk3YyBcdWFkZjggXHVhY2JkXHViODVjXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWM1ZjBcdWFjYjBcdWI0ZTRcdWM3NTggVVNBRE8gXHVjOTExIFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1YzczY1x1Yjg1YyBcdWQ1NThcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4NzRcdWM3NDAgXHVjNWI0XHViNWE0IFx1YzhmY1x1YzViNFx1YzljNCBNb29UdWJlIFx1YjNkOVx1YzYwMVx1YzBjMVx1YzVkMCBcdWIzMDBcdWQ1NzQsIFx1YWMxMiBLXHViOTdjIFx1YzgxNVx1ZDU3NFx1YzExYyBcdWFkZjggXHViM2Q5XHVjNjAxXHVjMGMxXHVhY2ZjIFVTQURPXHVhYzAwIEsgXHVjNzc0XHVjMGMxXHVjNzc4IFx1YmFhOFx1YjRlMCBcdWIzZDlcdWM2MDFcdWMwYzFcdWM3NzQgXHVjZDk0XHVjYzljXHViNDE4XHViM2M0XHViODVkIFx1ZDU2MCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWM4NzRcdWM3NDAgXHViMTA4XHViYjM0IFx1YjljZVx1Yzc0MCBcdWIzZDlcdWM2MDFcdWMwYzFcdWM3NzQgXHVjZDk0XHVjYzljXHViNDE4XHViYTc0IFx1YzE4Y1x1YjRlNFx1Yzc3NCBcdWM3N2NcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YmMyOVx1ZDU3NFx1YjQyMFx1YWU0YyBcdWJkMTAgXHVhYzcxXHVjODE1XHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNCEgXHVhZGY4XHViNzk4XHVjMTFjIFx1YWRmOFx1YjI5NCBLXHViOTdjIFx1YzgwMVx1YzgwOFx1ZDU1YyBcdWFjMTJcdWM3M2NcdWI4NWMgXHVhY2IwXHVjODE1XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViMThkXHViZDgwIFx1Yzg3NFx1Yzc0MCBcdWM1YjRcdWI1YTQgSyBcdWFjMTJcdWM1ZDAgXHViMzAwXHVkNTVjIFx1Y2Q5NFx1Y2M5YyBcdWIzZDlcdWM2MDFcdWMwYzFcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YmIzYlx1YjI5NCBcdWM5YzhcdWJiMzggXHVjNWVjXHViN2VjIFx1YWMxY1x1YzVkMCBcdWIyZjlcdWMyZTBcdWM3NzQgXHViMzAwXHViMmY1XHVkNTc0XHVjOGZjXHVhZTMwXHViOTdjIFx1YmMxNFx1Yjc4MFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBOXHVhY2ZjIFFcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7Jm5ic3A7USAmbGU7IDUsMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTi0xXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIxOGRcdWJkODAgXHVjODc0XHVjNzc0IFx1YzljMVx1YzgxMSBcdWM3YjAgXHViNDUwIFx1YjNkOVx1YzYwMVx1YzBjMSBcdWMzMGRcdWM3NTggVVNBRE9cdWFjMDAgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVjOTA0XHVjNzQwIFx1YzEzOCBcdWM4MTVcdWMyMTggcDxzdWI+aTxcL3N1Yj4sIHE8c3ViPmk8XC9zdWI+LCByPHN1Yj5pPFwvc3ViPiAoMSAmbGU7IHA8c3ViPmk8XC9zdWI+LCBxPHN1Yj5pPFwvc3ViPiZuYnNwOyZsZTsmbmJzcDtOLCAxICZsZTsgcjxzdWI+aTxcL3N1Yj4gJmxlOyAxLDAwMCwwMDAsMDAwKVx1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NThcdWIyOTRcdWIzNzAsIFx1Yzc3NFx1YjI5NCBcdWIzZDlcdWM2MDFcdWMwYzEgcDxzdWI+aTxcL3N1Yj5cdWM2NDAgcTxzdWI+aTxcL3N1Yj5cdWFjMDAgVVNBRE8gcjxzdWI+aTxcL3N1Yj5cdWI4NWMgXHVjMTFjXHViODVjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWM3NGNcdWM3NDQgXHViNzNiXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgUVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMThkXHViZDgwIFx1Yzg3NFx1Yzc1OCBRXHVhYzFjXHVjNzU4IFx1YzljOFx1YmIzOFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWM5MDRcdWM3NDAgXHViNDUwIFx1YzgxNVx1YzIxOCBrPHN1Yj5pPFwvc3ViPlx1YzY0MCB2PHN1Yj5pPFwvc3ViPigxICZsZTsgazxzdWI+aTxcL3N1Yj4gJmxlOyZuYnNwOzEsMDAwLDAwMCwwMDAsIDEgJmxlOyB2PHN1Yj5pPFwvc3ViPiAmbGU7IE4pXHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YjI5NFx1YjM3MCwgXHVjNzc0XHViMjk0IFx1Yzg3NFx1Yzc1OCBpXHViYzg4XHVjOWY4IFx1YzljOFx1YmIzOFx1Yzc3NCBcdWI5Y2NcdWM1N2QgSyA9IGs8c3ViPmk8XC9zdWI+XHViNzdjXHViYTc0IFx1YjNkOVx1YzYwMVx1YzBjMSB2PHN1Yj5pPFwvc3ViPlx1Yjk3YyBcdWJjZjRcdWFjZTAgXHVjNzg4XHViMjk0IFx1YzE4Y1x1YjRlNFx1YzVkMFx1YWM4YyBcdWJhODcgXHVhYzFjXHVjNzU4IFx1YjNkOVx1YzYwMVx1YzBjMVx1Yzc3NCBcdWNkOTRcdWNjOWNcdWI0MjAgXHVjOWMwIFx1YmIzYlx1YjI5NCBcdWFjODNcdWM3NzRcdWI3N2NcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YjczYlx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5RXHVhYzFjXHVjNzU4IFx1YzkwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIGlcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjE4ZFx1YmQ4MCBcdWM4NzRcdWM3NTggaVx1YmM4OFx1YzlmOCBcdWM5YzhcdWJiMzhcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YjJmNVx1YmNjMFx1Yzc3NCBcdWNkOWNcdWI4MjVcdWI0MThcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWIxOGRcdWJkODAgXHVjODc0XHVjNzQwIDFcdWJjODggXHViM2Q5XHVjNjAxXHVjMGMxXHVhY2ZjIDJcdWJjODggXHViM2Q5XHVjNjAxXHVjMGMxXHVjNzc0IFVTQURPIDNcdWM3NDQgXHVhYzAwXHVjOWMwXHVhY2UwLCAyXHViYzg4IFx1YjNkOVx1YzYwMVx1YzBjMVx1YWNmYyAzXHViYzg4IFx1YjNkOVx1YzYwMVx1YzBjMVx1Yzc3NCBVU0FETyAyXHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCwgMlx1YmM4OCBcdWIzZDlcdWM2MDFcdWMwYzFcdWFjZmMgNFx1YmM4OCBcdWIzZDlcdWM2MDFcdWMwYzFcdWM3NzQgVVNBRE8gNFx1Yjk3YyBcdWFjMDBcdWM5YzRcdWIyZTRcdWFjZTAgXHVkNTg4XHViMmU0LiBcdWM3NzRcdWFjODNcdWM1ZDAgXHVhZTMwXHViYzE4XHVkNTc0XHVjMTFjIDFcdWJjODggXHViM2Q5XHVjNjAxXHVjMGMxXHVhY2ZjIDNcdWJjODggXHViM2Q5XHVjNjAxXHVjMGMxXHVjNzU4IFVTQURPXHViMjk0IG1pbigzLDIpPTJcdWFjMDAgXHViNDE4XHVhY2UwLCAxXHViYzg4IFx1YjNkOVx1YzYwMVx1YzBjMVx1YWNmYyA0XHViYzg4IFx1YjNkOVx1YzYwMVx1YzBjMVx1Yzc1OCBVU0FET1x1YjI5NCBtaW4oMyw0KT0zXHVjNzc0IFx1YjQxOFx1YWNlMCwgM1x1YmM4OCBcdWIzZDlcdWM2MDFcdWMwYzFcdWFjZmMgNFx1YmM4OCBcdWIzZDlcdWM2MDFcdWMwYzFcdWM3NTggVVNBRE9cdWIyOTQgbWluKDIsNCk9Mlx1YWMwMCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjE4ZFx1YmQ4MCBcdWM4NzRcdWM3NDAgSz0xXHVjNzdjIFx1YjU0YyAyXHViYzg4IFx1YjNkOVx1YzYwMVx1YzBjMSwgSz0zXHVjNzdjIFx1YjU0YyAxXHViYzg4IFx1YjNkOVx1YzYwMVx1YzBjMSwgSz00XHVjNzdjIFx1YjU0YyAxXHViYzg4IFx1YjNkOVx1YzYwMVx1YzBjMVx1Yzc0NCBcdWJjZjRcdWJhNzQgXHVhYzAxXHVhYzAxIFx1YmE4NyBcdWFjMWNcdWM3NTggXHViM2Q5XHVjNjAxXHVjMGMxXHVjNzc0IFx1Y2Q5NFx1Y2M5Y1x1YjQyMFx1YWU0YyBcdWFkODFcdWFlMDhcdWQ1NzRcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBLPTFcdWM3N2MgXHViNTRjIDJcdWJjODggXHViM2Q5XHVjNjAxXHVjMGMxXHVjNWQwXHVjMTFjIFx1Y2Q5NFx1Y2M5Y1x1YjQxOFx1YjI5NCBcdWIzZDlcdWM2MDFcdWMwYzFcdWM3NDAgMSwgMywgNFx1YmM4OCBcdWIzZDlcdWM2MDFcdWMwYzFcdWM3NzRcdWIyZTQuIEs9NFx1Yzc3YyBcdWI1NGMgMVx1YmM4OCBcdWIzZDlcdWM2MDFcdWMwYzFcdWM3M2NcdWI4NWNcdWJkODBcdWQxMzAgXHVjZDk0XHVjYzljXHViNDE4XHViMjk0IFx1YjNkOVx1YzYwMVx1YzBjMVx1Yzc0MCBcdWM1YzZcdWIyZTQuIFx1YWRmOFx1YjdlY1x1YjA5OCBLPTNcdWM3N2NcdWI1NGNcdWIyOTQgMVx1YmM4OCBcdWIzZDlcdWM2MDFcdWMwYzFcdWM1ZDBcdWMxMWMgMlx1YmM4OCBcdWIzZDlcdWM2MDFcdWMwYzFcdWFjZmMgNFx1YmM4OCBcdWIzZDlcdWM2MDFcdWMwYzFcdWM3NzQgXHVjZDk0XHVjYzljXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTU1OTEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNb29UdWJlIChTaWx2ZXIpIiwiZGVzY3JpcHRpb24iOiI8cD5JbiBoaXMgc3BhcmUgdGltZSwgRmFybWVyIEpvaG4gaGFzIGNyZWF0ZWQgYSBuZXcgdmlkZW8tc2hhcmluZyBzZXJ2aWNlLCB3aGljaCBoZSBuYW1lcyBNb29UdWJlLiBPbiBNb29UdWJlLCBGYXJtZXIgSm9obiYjMzk7cyBjb3dzIGNhbiByZWNvcmQsIHNoYXJlLCBhbmQgZGlzY292ZXIgbWFueSBhbXVzaW5nIHZpZGVvcy4gSGlzIGNvd3MgYWxyZWFkeSBoYXZlIHBvc3RlZCAkTiQgdmlkZW9zICgkMSBcXGxlcSBOIFxcbGVxIDUwMDAkKSwgY29udmVuaWVudGx5IG51bWJlcmVkICQxIFxcbGRvdHMgTiQuIEhvd2V2ZXIsIEZKIGNhbiYjMzk7dCBxdWl0ZSBmaWd1cmUgb3V0IGhvdyB0byBoZWxwIGhpcyBjb3dzIGZpbmQgbmV3IHZpZGVvcyB0aGV5IG1pZ2h0IGxpa2UuPFwvcD5cclxuXHJcbjxwPkZKIHdhbnRzIHRvIGNyZWF0ZSBhIGxpc3Qgb2YgJnF1b3Q7c3VnZ2VzdGVkIHZpZGVvcyZxdW90OyBmb3IgZXZlcnkgTW9vVHViZSB2aWRlby4gVGhpcyB3YXksIGNvd3Mgd2lsbCBiZSByZWNvbW1lbmRlZCB0aGUgdmlkZW9zIG1vc3QgcmVsZXZhbnQgdG8gdGhlIG9uZXMgdGhleSBhbHJlYWR5IHdhdGNoLjxcL3A+XHJcblxyXG48cD5GSiBkZXZpc2VzIGEgbWV0cmljIG9mICZxdW90O3JlbGV2YW5jZSwmcXVvdDsgd2hpY2ggZGV0ZXJtaW5lcywgYXMgdGhlIG5hbWUgc3VnZ2VzdHMsIGhvdyByZWxldmFudCB0d28gdmlkZW9zIGFyZSB0byBlYWNoIG90aGVyLiBIZSBwaWNrcyAkTi0xJCBwYWlycyBvZiB2aWRlb3MgYW5kIG1hbnVhbGx5IGNvbXB1dGVzIHRoZWlyIHBhaXJ3aXNlIHJlbGV2YW5jZS4gVGhlbiwgRkogdmlzdWFsaXplcyBoaXMgdmlkZW9zIGFzIGEgbmV0d29yaywgd2hlcmUgZWFjaCB2aWRlbyBpcyBhIG5vZGUgYW5kIHRoZSAkTi0xJCBwYWlycyBvZiB2aWRlb3MgaGUgbWFudWFsbHkgY29uc2lkZXJlZCBhcmUgY29ubmVjdGVkLiBDb252ZW5pZW50bHksIEZKIGhhcyBwaWNrZWQgaGlzICROLTEkIHBhaXJzIHNvIHRoYXQgYW55IHZpZGVvIGNhbiBiZSByZWFjaGVkIGZyb20gYW55IG90aGVyIHZpZGVvIGFsb25nIGEgcGF0aCBvZiBjb25uZWN0aW9ucyBpbiBleGFjdGx5IG9uZSB3YXkuIEZKIGRlY2lkZXMgdGhhdCB0aGUgcmVsZXZhbmNlIG9mIGFueSBwYWlyIG9mIHZpZGVvcyBzaG91bGQgYmUgZGVmaW5lZCBhcyB0aGUgbWluaW11bSByZWxldmFuY2Ugb2YgYW55IGNvbm5lY3Rpb24gYWxvbmcgdGhpcyBwYXRoLjxcL3A+XHJcblxyXG48cD5GYXJtZXIgSm9obiB3YW50cyB0byBwaWNrIGEgdmFsdWUgJEskIHNvIHRoYXQgbmV4dCB0byBhbnkgZ2l2ZW4gTW9vVHViZSB2aWRlbywgYWxsIG90aGVyIHZpZGVvcyB3aXRoIHJlbGV2YW5jZSBhdCBsZWFzdCAkSyQgdG8gdGhhdCB2aWRlbyB3aWxsIGJlIHN1Z2dlc3RlZC4gSG93ZXZlciwgRkogaXMgd29ycmllZCB0aGF0IHRvbyBtYW55IHZpZGVvcyB3aWxsIGJlIHN1Z2dlc3RlZCB0byBoaXMgY293cywgd2hpY2ggY291bGQgZGlzdHJhY3QgdGhlbSBmcm9tIG1pbGsgcHJvZHVjdGlvbiEgVGhlcmVmb3JlLCBoZSB3YW50cyB0byBjYXJlZnVsbHkgc2V0IGFuIGFwcHJvcHJpYXRlIHZhbHVlIG9mICRLJC4gRmFybWVyIEpvaG4gd291bGQgbGlrZSB5b3VyIGhlbHAgYW5zd2VyaW5nIGEgbnVtYmVyIG9mIHF1ZXN0aW9ucyBhYm91dCB0aGUgc3VnZ2VzdGVkIHZpZGVvcyBmb3IgY2VydGFpbiB2YWx1ZXMgb2YgJEskLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgJE4kIGFuZCAkUSQgKCQxIFxcbGVxIFEgXFxsZXEgNTAwMCQpLjxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCAkTi0xJCBsaW5lcyBlYWNoIGRlc2NyaWJlIGEgcGFpciBvZiB2aWRlb3MgRkogbWFudWFsbHkgY29tcGFyZXMuIEVhY2ggbGluZSBpbmNsdWRlcyB0aHJlZSBpbnRlZ2VycyAkcF9pJCwgJHFfaSQsIGFuZCAkcl9pJCAoJDEgXFxsZXEgcF9pLCBxX2kgXFxsZXEgTiwgMSBcXGxlcSByX2kgXFxsZXEgMSwwMDAsMDAwLDAwMCQpLCBpbmRpY2F0aW5nIHRoYXQgdmlkZW9zICRwX2kkIGFuZCAkcV9pJCBhcmUgY29ubmVjdGVkIHdpdGggcmVsZXZhbmNlICRyX2kkLjxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCAkUSQgbGluZXMgZGVzY3JpYmUgRmFybWVyIEpvaG4mIzM5O3MgJFEkIHF1ZXN0aW9ucy4gRWFjaCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycywgJGtfaSQgYW5kICR2X2kkICgkMSBcXGxlcSBrX2kgXFxsZXEgMSwwMDAsMDAwLDAwMCwgMSBcXGxlcSB2X2kgXFxsZXEgTiQpLCBpbmRpY2F0aW5nIHRoYXQgRkomIzM5O3MgJGkkdGggcXVlc3Rpb24gYXNrcyBob3cgbWFueSB2aWRlb3Mgd2lsbCBiZSBzdWdnZXN0ZWQgdG8gdmlld2VycyBvZiB2aWRlbyAkdl9pJCBpZiAkSyA9IGtfaSQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0ICRRJCBsaW5lcy4gT24gbGluZSAkaSQsIG91dHB1dCB0aGUgYW5zd2VyIHRvIEZKJiMzOTtzICRpJHRoIHF1ZXN0aW9uLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5GYXJtZXIgSm9obiBmaW5kcyB0aGF0IHZpZGVvcyBvbmUgYW5kIHR3byBoYXZlIHJlbGV2YW5jZSB0aHJlZSwgdGhhdCB2aWRlb3MgdHdvIGFuZCB0aHJlZSBoYXZlIHJlbGV2YW5jZSB0d28sIGFuZCB0aGF0IHZpZGVvcyB0d28gYW5kIGZvdXIgaGF2ZSByZWxldmFuY2UgZm91ci4gQmFzZWQgb24gdGhpcywgdmlkZW9zIG9uZSBhbmQgdGhyZWUgaGF2ZSByZWxldmFuY2UgbWluKDMsIDIpID0gMiwgdmlkZW9zIG9uZSBhbmQgZm91ciBoYXZlIHJlbGV2YW5jZSBtaW4oMywgNCkgPSAzLCBhbmQgdmlkZW9zIHRocmVlIGFuZCBmb3VyIGhhdmUgcmVsZXZhbmNlIG1pbigyLCA0KSA9IDIuPFwvcD5cclxuXHJcbjxwPkZhcm1lciBKb2huIHdhbnRzIHRvIGtub3cgaG93IG1hbnkgdmlkZW9zIHdpbGwgYmUgc3VnZ2VzdGVkIGZyb20gdmlkZW8gdHdvIGlmICRLPTEkLCBmcm9tIHZpZGVvIG9uZSBpZiAkSz0zJCwgYW5kIGZyb20gdmlkZW8gb25lIGlmICRLPTQkLiBXZSBzZWUgdGhhdCB3aXRoICRLPTEkLCB2aWRlb3MgMSwgMywgYW5kIDQgd2lsbCBiZSBzdWdnZXN0ZWQgb24gdmlkZW8gdHdvLiBXaXRoICRLPTQkLCBubyB2aWRlb3Mgd2lsbCBiZSBzdWdnZXN0ZWQgZnJvbSB2aWRlbyBvbmUuIFdpdGggJEs9MyQsIGhvd2V2ZXIsIHZpZGVvcyAyIGFuZCA0IHdpbGwgYmUgc3VnZ2VzdGVkIGZyb20gdmlkZW8gb25lLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > USA Computing Olympiad > 2017-2018 Season > USACO 2018 January Contest > Silver 3번

  • 문제의 오타를 찾은 사람: hschoi1104
  • 문제를 번역한 사람: ryute