#P4444. [Scoi2015]国旗计划
[Scoi2015]国旗计划
[SCOI 2015] 国旗计划
题目描述
一条环形边境线上有 个边防站,顺时针编号 到 ,其中第 站的下一站是第 站。
有 名战士。第 名战士能负责从 站沿顺时针走到 站的整段边境,包含两端;若 ,这段路线经过第 站和第 站。任一战士负责的区间都不会被另一名战士的区间包含。所有战士的区间合起来覆盖整条边境。
对每一名战士 单独回答:在他必须参加的前提下,最少要选多少名战士(含他本人),使各自的区间合起来覆盖边境一整圈?
输入格式
第一行两个正整数 ,其中 ,。
接下来 行。第 行两个整数 (),表示第 名战士的起站和终站。
输出格式
输出一行 个整数。第 个整数表示第 名战士必须参加时的最少人数。
样例 #1
样例输入 #1
4 8
2 5
4 7
6 1
7 3
样例输出 #1
3 3 4 3