5410: Intervals on the Ring

There is a ring of numbers consisting of 1 to nsequentially. For every number i(1≤i≤n−1) , i and i+1 are adjacent to each other. Particularly, n and 1 are adjacent. We use [l,r] to describe an interval on the ring. Formally, if l≤r , then the interval [l,r] is equivalent to the set {l,l+1,…,r−1,r} . Otherwise, the interval [l,r] is equivalent to {l,l+1,…,n,1,…,r−1,r} .

Yukikaze has m non-intersecting intervals. She wants you to construct a set of intervals such that the intersection of them is the union of the m intervals that Yukikaze has. The intersection of the intervals is the set of integers that the intervals have in common.

For each test case, if the answer doesn't exist, output −1 in a line. Otherwise, output an integer k indicating the number of intervals you construct in a line. Then output the k intervals in k lines. The number of intervals you used should never be less than one or greater than 2000.

If there are multiple solutions, print any. Don't print any extra spaces at the end of each line.

2
3 1
2 2
4 2
1 1
3 3

1
2 2
2
3 1
1 3