luogu#P11055. Yet another ZP problem

Yet another ZP problem

题目描述

从左到右排列着 nn 个点,编号分别为 1,2,,n1,2,\dots,n

你要在他们之间连一些边,记边集为 E={(x,y)  1x<yn}E=\{(x,y)\ |\ 1\leq x<y\leq n\}

我们称边集 EE 满足限制 [l,r][l,r],当且仅当存在 (x,y)E(x,y)\in E 使得 [x[l,r]]+[y[l,r]]=1[x\in[l,r]]+[y\in[l,r]]=1

基础地,我们希望对所有 1in1\leq i\leq n 满足限制 [i,i][i,i]

在此基础上,输入还给定了额外的 mm 个限制 [li,ri][l_i,r_i]1li<rin1\leq l_i<r_i\leq n 并且 [li,ri][1,n][l_i,r_i]\neq [1,n])。

请问 E|E| 最小是多少,在此基础上给出一组合法构造。可以证明,合法的 EE 总是存在的。

对于形如 [P][P] 的表达式,当且仅当命题 PP 为真时其取值为 11,否则取值为 00

输入格式

第一行输入两个整数 n,mn,m

接下来 mm 行每行两个正整数 li,ril_i,r_i

输出格式

第一行输出一个数代表 E|E|

接下来 E|E| 行,每行两个数 x,yx,y 代表一条边,注意你需要保证 1x<yn1\le x<y\le n

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

提示

样例解释

对于限制 [1,1][1, 1],存在边 (1,4)(1, 4) 使得 [1[1,1]]+[4[1,1]]=1[1 \in [1, 1]] + [4 \in [1, 1]] = 1

对于限制 [3,4][3, 4],存在边 (1,4)(1, 4) 使得 [1[3,4]]+[4[3,4]]=1[1 \in [3, 4]] + [4 \in [3, 4]] = 1

对于限制 [2,2][2, 2],存在边 (2,3)(2, 3) 使得 [2[2,2]]+[3[2,2]]=1[2 \in [2, 2]] + [3 \in [2, 2]] = 1

数据范围

对于所有数据,保证 3n1043\leq n\leq 10^40m1050\leq m\leq 10^51li<rin1\le l_i<r_i\le n[li,ri][1,n][l_i,r_i]\ne [1,n]

测试点编号 特殊性质
151\sim 5 n,m5n,m\le 5
676\sim 7 m=0m=0
8118\sim 11 ri<li+1r_i<l_{i+1}
121412\sim 14 li=1l_i=1
152015\sim 20

对于第 ii 个测试点,保证 nn 的奇偶性与 ii 的奇偶性相同,mm 的奇偶性与 i2+1\lfloor\frac{i}{2}\rfloor+1 的奇偶性相同。