Minimum Edge Set with Cut Constraints

We are given n points arranged from left to right, labeled from 1 to n. Consider all possible edges between these points, i.e. the set of pairs \(E = \{(x,y)\mid 1 \le x < y \le n\}\).

An edge set \(E\) is said to satisfy the constraint \([l,r]\) if and only if there exists an edge \((x,y) \in E\) such that \[ [ x \in [l, r] ] + [ y \in [l, r] ] = 1, \] where for any proposition \(P\), \([P]\) is defined to be \(1\) if \(P\) is true and \(0\) otherwise.

In addition to the extra constraints given in the input, it is required that for every \(1 \le i \le n\) the constraint \([i,i]\) is satisfied, i.e. every point must be incident to at least one edge.

You are also given m extra constraints \([l_i, r_i]\) (with \(1 \le l_i < r_i \le n\) and \([l_i, r_i] \neq [1,n]\)). Your task is to construct an edge set \(E\) of minimum size satisfying all these constraints, and output one valid construction. It can be proven that a valid \(E\) always exists.

Note: The expression \([P]\) equals \(1\) if the proposition \(P\) is true, and \(0\) otherwise.

inputFormat

The first line contains two integers n and m (n \(\geq 2\)). Each of the next m lines contains two integers \(l_i\) and \(r_i\) representing an extra constraint \([l_i, r_i]\). It is guaranteed that \(1 \leq l_i < r_i \leq n\) and \([l_i, r_i] \neq [1, n]\).

outputFormat

On the first line, output a single integer, the minimum number of edges \(|E|\) in your construction. Then output \(|E|\) lines, each containing two integers x and y (with \(1 \le x < y \le n\)), representing an edge in \(E\). If there are multiple answers, you may output any of them.

Explanation: A valid construction is guaranteed to exist. One simple construction is to form a spanning tree, for instance by connecting the points in a chain: (1,2), (2,3), ..., (n-1, n).

sample

2 0

1
1 2