题目描述
从左到右排列着 n 个点,编号分别为 1,2,…,n。
你要在他们之间连一些边,记边集为 E={(x,y) ∣ 1≤x<y≤n}。
我们称边集 E 满足限制 [l,r],当且仅当存在 (x,y)∈E 使得 [x∈[l,r]]+[y∈[l,r]]=1。
基础地,我们希望对所有 1≤i≤n 满足限制 [i,i]。
在此基础上,输入还给定了额外的 m 个限制 [li,ri](1≤li<ri≤n 并且 [li,ri]=[1,n])。
请问 ∣E∣ 最小是多少,在此基础上给出一组合法构造。可以证明,合法的 E 总是存在的。
对于形如 [P] 的表达式,当且仅当命题 P 为真时其取值为 1,否则取值为 0。
输入格式
第一行输入两个整数 n,m。
接下来 m 行每行两个正整数 li,ri。
输出格式
第一行输出一个数代表 ∣E∣。
接下来 ∣E∣ 行,每行两个数 x,y 代表一条边,注意你需要保证 1≤x<y≤n。
4 3
1 2
3 4
1 2
2
1 4
2 3
提示
样例解释
对于限制 [1,1],存在边 (1,4) 使得 [1∈[1,1]]+[4∈[1,1]]=1。
对于限制 [3,4],存在边 (1,4) 使得 [1∈[3,4]]+[4∈[3,4]]=1。
对于限制 [2,2],存在边 (2,3) 使得 [2∈[2,2]]+[3∈[2,2]]=1。
数据范围
对于所有数据,保证 3≤n≤104,0≤m≤105,1≤li<ri≤n,[li,ri]=[1,n]。
测试点编号 |
特殊性质 |
1∼5 |
n,m≤5 |
6∼7 |
m=0 |
8∼11 |
ri<li+1 |
12∼14 |
li=1 |
15∼20 |
无 |
对于第 i 个测试点,保证 n 的奇偶性与 i 的奇偶性相同,m 的奇偶性与 ⌊2i⌋+1 的奇偶性相同。