A - Inside or Outside
Source: atcoder
Difficulty: 700

Problem Statement
There is an integer sequence
x = (x_1, \ldots, x_N)
, which is initialized with
x_1 = \cdots = x_N = 0
.
You will perform
M
operations on this integer sequence. In the
i
-th operation, you are given an integer pair
(L_i, R_i)
such that
1 \leq L_i \leq R_i \leq N
, and you must perform
exactly one
of the following three operations:
Operation
0
: Do nothing. This operation incurs a cost of
0
.
Operation
1
: For each integer
j
with
1 \leq j \leq N
, if
L_i \leq j \leq R_i
holds
, set
x_j = 1
. This operation incurs a cost of
1
.
Operation
2
: For each integer
j
with
1 \leq j \leq N
, if
L_i \leq j \leq R_i
does not hold
, set
x_j = 1
. This operation incurs a cost of
1
.
Your goal is to make
x_1 = \cdots = x_N = 1
hold at the end. Determine whether this goal can be achieved. If it can be achieved, present one way to achieve it where the total cost of the operations is minimized.
Constraints
1 \leq N \leq 1000000
1 \leq M \leq 200000
1 \leq L_i \leq R_i \leq N
All input values are integers.
Input
The input is given from Standard Input in the following format:
N
M
L_1
R_1
\vdots
L_M
R_M
Output
If the goal is not achievable, print
-1
.
If the goal is achievable, print one way to achieve it where the total cost of the operations is minimized, in the following format, where
K
is the minimum total cost of the operations, and
\mathrm{op}_i
is the type of operation (
0
,
1
, or
2
) chosen for the
i
-th operation.
K
\mathrm{op}_1
\cdots
\mathrm{op}_M
If there are multiple ways that minimize the total cost, printing any one of them is accepted.
Sample Input 1
5 4
2 4
3 5
1 4
2 5
Sample Output 1
2
2 0 1 0
In the sample output,
x
changes as follows:
Initially,
x = (0,0,0,0,0)
.
In the 1st operation, Operation
2
is performed.
x_1
and
x_5
become 1, so
x = (1,0,0,0,1)
.
In the 2nd operation, Operation
0
is performed.
x
remains
(1,0,0,0,1)
.
In the 3rd operation, Operation
1
is performed.
x_1, x_2, x_3, x_4
become 1, so
x = (1,1,1,1,1)
.
In the 4th operation, Operation
0
is performed.
x
remains
(1,1,1,1,1)
.
Sample Input 2
5 4
1 3
1 5
2 4
3 5
Sample Output 2
1
0 1 0 0
Sample Input 3
5 2
1 3
2 5
Sample Output 3
2
1 1
Sample Input 4
5 2
1 3
2 4
Sample Output 4
-1

C++ solution:
#include <bits/stdc++.h>
using namespace std;
const int N=2e6+5;
int n,m;
struct node {
	int l,r,id;
} a[N];
int l[N],r[N];
bool cmp(node a,node b) {
	if(a.l!=b.l) return a.l<b.l;
	return a.r<b.r;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1; i<=m; i++) cin>>a[i].l>>a[i].r,a[i].id=i;
	for(int i=1; i<=m; i++) {
		if(a[i].l==1&&a[i].r==n) {
			cout<<1<<"\n";
			for(int i=1; i<=m; i++) {
				if(a[i].l==1&&a[i].r==n) cout<<1<<" ";
				else cout<<0<<" ";
			}
			return 0;
		}
	}
	sort(a+1,a+1+m,cmp);
	int minr = 1, maxr = 1;
	for (int j = 2; j <= m; j++) {
		if (a[minr].r < a[j].l) {
			cout << "2\n";
			for (int i = 1; i <= m; i++) {
				if (i == a[minr].id || i == a[j].id)
					cout << "2 ";
				else
					cout << "0 ";
			}
			return 0;
		}
		if (a[maxr].r >= a[j].r) {
			cout << "2\n";
			for (int i = 1; i <= m; i++) {
				if (i == a[maxr].id)
					cout << "1 ";
				else if (i == a[j].id)
					cout << "2 ";
				else
					cout << "0 ";
			}
			return 0;
		}
		if (a[j].l == a[j - 1].l) {
			cout << "2\n";
			for (int i = 1; i <= m; i++) {
				if (i == a[j - 1].id)
					cout << "2 ";
				else if (i == a[j].id)
					cout << "1 ";
				else
					cout << "0 ";
			}
			return 0;
		}
		if (a[minr].r > a[j].r) minr = j;
		if (a[maxr].r < a[j].r) maxr = j;
	}
	if (a[1].l == 1 && a[m].r == n) {
		cout << "2\n";
		for (int i = 1; i <= m; i++) {
			if (i == a[1].id)
				cout << "1 ";
			else if (i == a[m].id)
				cout << "1 ";
			else
				cout << "0 ";
		}
		return 0;
	}
	if (m <= 2) {
		cout << "-1";
		return 0;
	} else {
		cout << "3\n";
		for (int i = 1; i <= m; i++) {
			if (i == a[1].id)
				cout << "2 ";
			else if (i == a[2].id)
				cout << "1 ";
			else if (i == a[3].id)
				cout << "2 ";
			else
				cout << "0 ";
		}
	}
	return 0;
}
/*
5 4
2 4
3 5
1 4
2 5
*/

Go solution:
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"sort"
	"strconv"
)

var iost *Iost

type Iost struct {
	Scanner *bufio.Scanner
	Writer  *bufio.Writer
}

func NewIost(fp io.Reader, wfp io.Writer) *Iost {
	const BufSize = 2000005
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, BufSize), BufSize)
	return &Iost{Scanner: scanner, Writer: bufio.NewWriter(wfp)}
}
func (i *Iost) Text() string {
	if !i.Scanner.Scan() {
		panic("scan failed")
	}
	return i.Scanner.Text()
}
func (i *Iost) Atoi(s string) int                 { x, _ := strconv.Atoi(s); return x }
func (i *Iost) GetNextInt() int                   { return i.Atoi(i.Text()) }
func (i *Iost) Atoi64(s string) int64             { x, _ := strconv.ParseInt(s, 10, 64); return x }
func (i *Iost) GetNextInt64() int64               { return i.Atoi64(i.Text()) }
func (i *Iost) Atof64(s string) float64           { x, _ := strconv.ParseFloat(s, 64); return x }
func (i *Iost) GetNextFloat64() float64           { return i.Atof64(i.Text()) }
func (i *Iost) Print(x ...interface{})            { fmt.Fprint(i.Writer, x...) }
func (i *Iost) Printf(s string, x ...interface{}) { fmt.Fprintf(i.Writer, s, x...) }
func (i *Iost) Println(x ...interface{})          { fmt.Fprintln(i.Writer, x...) }
func isLocal() bool                               { return os.Getenv("NICKEL") == "BACK" }
func main() {
	fp := os.Stdin
	wfp := os.Stdout
	if isLocal() {
		fp, _ = os.Open(os.Getenv("WELL_EVERYBODY_LIES_TOO_MUCH"))
	}
	iost = NewIost(fp, wfp)
	defer func() {
		iost.Writer.Flush()
	}()
	solve()
}
func solve() {
	n := iost.GetNextInt()
	m := iost.GetNextInt()
	ll := make([]int, m)
	rr := make([]int, m)
	for i := 0; i < m; i++ {
		ll[i] = iost.GetNextInt()
		rr[i] = iost.GetNextInt()
	}
	one := func() bool {
		for i := 0; i < m; i++ {
			if ll[i] == 1 && rr[i] == n {
				iost.Println(1)
				for j := 0; j < m; j++ {
					if j > 0 {
						iost.Print(" ")
					}
					if i == j {
						iost.Print(1)
						continue
					}
					iost.Print(0)
				}
				iost.Println("")
				return true
			}
		}
		return false
	}
	if one() {
		return
	}
	twotwo := func() bool {
		lmax := 0
		rmin := 0
		for i := 0; i < m; i++ {
			if ll[lmax] < ll[i] {
				lmax = i
			}
			if rr[rmin] > rr[i] {
				rmin = i
			}
		}
		if rr[rmin] < ll[lmax] {
			iost.Println(2)
			for i := 0; i < m; i++ {
				if i > 0 {
					iost.Print(" ")
				}
				if i == lmax || i == rmin {
					iost.Print(2)
					continue
				}
				iost.Print(0)
			}
			iost.Println("")
			return true
		}
		return false
	}
	if twotwo() {
		return
	}
	onetwo := func() bool {
		ii := make([]int, m)
		for i := 0; i < m; i++ {
			ii[i] = i
		}
		sort.Slice(ii, func(i, j int) bool {
			if ll[ii[i]] == ll[ii[j]] {
				return rr[ii[i]] > rr[ii[j]]
			}
			return ll[ii[i]] < ll[ii[j]]
		})
		rmax := 0
		for i := 1; i < m; i++ {
			if rr[ii[i]] <= rr[ii[rmax]] {
				iost.Println(2)
				for j := 0; j < m; j++ {
					if j > 0 {
						iost.Print(" ")
					}
					if ii[i] == j {
						iost.Print(2)
						continue
					}
					if ii[rmax] == j {
						iost.Print(1)
						continue
					}
					iost.Print(0)
				}
				iost.Println("")
				return true
			}
			rmax = i
		}
		return false
	}
	if onetwo() {
		return
	}
	oneone := func() bool {
		lmin := -1
		rmax := -1
		for i := 0; i < m; i++ {
			if ll[i] == 1 {
				if rmax == -1 || rr[rmax] < rr[i] {
					rmax = i
				}
			}
			if rr[i] == n {
				if lmin == -1 || ll[lmin] > ll[i] {
					lmin = i
				}
			}
		}
		if lmin == -1 || rmax == -1 {
			return false
		}
		if rr[rmax] >= ll[lmin] {
			iost.Println(2)
			for i := 0; i < m; i++ {
				if i > 0 {
					iost.Print(" ")
				}
				if i == lmin || i == rmax {
					iost.Print(1)
					continue
				}
				iost.Print(0)
			}
			iost.Println("")
			return true
		}
		return false
	}
	if oneone() {
		return
	}
	if m < 3 {
		iost.Println(-1)
		return
	}
	three := func() {
		lmax := 0
		rmin := 0
		for i := 0; i < m; i++ {
			if ll[lmax] < ll[i] {
				lmax = i
			}
			if rr[rmin] > rr[i] {
				rmin = i
			}
		}
		iost.Println(3)
		ans := 1
		for i := 0; i < m; i++ {
			if i > 0 {
				iost.Print(" ")
			}
			if i == lmax || i == rmin {
				iost.Print(2)
				continue
			}
			iost.Print(ans)
			ans = 0
		}
		iost.Println("")
	}
	three()
}

Java solution:
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] sa = br.readLine().split(" ");
		int n = Integer.parseInt(sa[0]);
		int m = Integer.parseInt(sa[1]);
		Obj[] arr = new Obj[m];
		PriorityQueue<Obj> que = new PriorityQueue<>((o1, o2) -> {
			if (o1.l != o2.l) {
				return o1.l - o2.l;
			}
			return o2.r - o1.r;
		});
		for (int i = 0; i < m; i++) {
			sa = br.readLine().split(" ");
			Obj o = new Obj();
			o.i = i;
			o.l = Integer.parseInt(sa[0]);
			o.r = Integer.parseInt(sa[1]);
			arr[i] = o;
			que.add(o);
		}
		br.close();

		Obj minl = arr[0];
		Obj minr = arr[0];
		Obj maxl = arr[0];
		Obj maxr = arr[0];
		for (int i = 0; i < m; i++) {
			Obj o = arr[i];
			if (o.l == 1 && o.r == n) {
				System.out.println(1);
				StringBuilder sb = new StringBuilder();
				for (int j = 0; j < m; j++) {
					if (j == i) {
						sb.append(1).append(' ');
					} else {
						sb.append(0).append(' ');
					}
				}
				sb.deleteCharAt(sb.length() - 1);
				System.out.println(sb.toString());
				return;
			}

			if (o.l < minl.l || o.l == 1 && o.r > minl.r) minl = o;
			if (o.r < minr.r) minr = o;
			if (o.l > maxl.l) maxl = o;
			if (o.r > maxr.r || o.r == n && o.l < maxr.l) maxr = o;
		}

		if (minr.r < maxl.l) {
			minr.a = 2;
			maxl.a = 2;
			out(arr);
			return;
		}
		if (minl.l == 1 && maxr.l <= minl.r + 1 && maxr.r == n) {
			minl.a = 1;
			maxr.a = 1;
			out(arr);
			return;
		}

		List<Obj> list = new ArrayList<>();
		Obj o1 = que.poll();
		list.add(o1);
		while (!que.isEmpty()) {
			Obj o = que.poll();
			if (o.r <= o1.r) {
				o1.a = 1;
				o.a = 2;
				out(arr);
				return;
			} else {
				o1 = o;
			}
			list.add(o);
		}

		if (list.size() >= 3) {
			list.get(0).a = 2;
			list.get(1).a = 1;
			list.get(2).a = 2;
			out(arr);
		} else {
			System.out.println(-1);
		}
	}

	static void out(Obj[] arr) {
		int ans = 0;
		StringBuilder sb = new StringBuilder();
		for (Obj o : arr) {
			sb.append(o.a).append(' ');
			if (o.a != 0) {
				ans++;
			}
		}
		sb.deleteCharAt(sb.length() - 1);
		System.out.println(ans);
		System.out.println(sb.toString());
	}

	static class Obj {
		int i, l, r, a;
	}
}

JavaScript solution:
"use strict";
var input=require("fs").readFileSync("/dev/stdin","utf8");
var cin=input.split(/ |\n/),cid=0;
function next(){return +cin[cid++];}
function nextstr(){return cin[cid++];}
function nextbig(){return BigInt(cin[cid++]);}
function nexts(n,a){return a?cin.slice(cid,cid+=n):cin.slice(cid,cid+=n).map(a=>+a);}
function nextssort(n,a){return a?cin.slice(cid,cid+=n).map(a=>+a).sort((a,b)=>b-a):cin.slice(cid,cid+=n).map(a=>+a).sort((a,b)=>a-b);}
function nextm(h,w,a){var r=[],i=0;if(a)for(;i<h;i++)r.push(cin.slice(cid,cid+=w));else for(;i<h;i++)r.push(cin.slice(cid,cid+=w).map(a=>+a));return r;}
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill().map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill().map(x=>"+r+")";return eval(r);}
var streams=[];function print(s){streams.push(s);}

var myOut = main();
if(myOut !== undefined)console.log(String(myOut));
if(streams.length)console.log(streams.join(" "));

function main(){
  var q = 1;
  while(q--)console.log(solve());
}

function solve(){
  var [n,m] = nexts(2);
  var lr = [];
  var ans = xArray(0,m);
  var lid = -1, rid = -1, lmx = -1, rmn = n+1;
  for(var i = 0; i < m; i++){
    var [l,r] = nexts(2);
    if(l === 1 && r === n){
      ans[i] = 1;
      streams = ans;
      return 1;
    }
    if(l === 1 && lmx < r){
      lid = i;
      lmx = r;
    }
    if(r === n && rmn > l){
      rid = i;
      rmn = l;
    }
    if(lmx+1 >= rmn){
      ans[lid] = 1;
      ans[rid] = 1;
      streams = ans;
      return 2;
    }
    lr.push([l,r,i]);
  }
  if(m === 1)return -1;
  lr.sort((a,b)=>a[0] !== b[0] ? a[0]-b[0] : b[1]-a[1]);
  var rx = 0, xid = -1;
  var rmn = n+1, rmnid = -1;
  for(var i = 0; i < m; i++){
    var [l,r,id] = lr[i];
    if(rx >= r){
      ans[xid] = 1;
      ans[id] = 2;
      streams = ans;
      return 2;
    }
    if(rmn < l){
      ans[rmnid] = ans[id] = 2;
      streams = ans;
      return 2;
    }else if(rmn > r){
      rmn = r;
      rmnid = id;
    }
    rx = r;
    xid = id;
  }
  if(m <= 2)return -1;
  ans[lr[0][2]] = ans[lr[2][2]] = 1;
  ans[lr[1][2]] = 2;
  streams = ans;
  return 3;
}

Python solution:
import sys, random
input = lambda : sys.stdin.readline().rstrip()


write = lambda x: sys.stdout.write(x+"\n"); writef = lambda x: print("{:.12f}".format(x))
debug = lambda x: sys.stderr.write(x+"\n")
YES="Yes"; NO="No"; pans = lambda v: print(YES if v else NO); INF=10**18
LI = lambda v=0: list(map(lambda i: int(i)-v, input().split())); II=lambda : int(input()); SI=lambda : [ord(c)-ord("a") for c in input()]
def debug(_l_):
    for s in _l_.split():
        print(f"{s}={eval(s)}", end=" ")
    print()
def dlist(*l, fill=0):
    if len(l)==1:
        return [fill]*l[0]
    ll = l[1:]
    return [dlist(*ll, fill=fill) for _ in range(l[0])]

n,m = LI()
lr = [LI() for _ in range(m)]
def main(n,m,lr):
    ans = [0]*m
    for i,(l,r) in enumerate(lr):
        if l==1 and r==n:
            print(1)
            ans[i] = 1
            print(*ans)
            break
    else:
        rmin = (INF,None)
        lmax = (-INF,None)
        for i,(l,r) in enumerate(lr):
            if r<rmin[0]:
                rmin = (r,i)
            if l>lmax[0]:
                lmax = (l,i)
        if rmin[0]<lmax[0]:
            print(2)
            ans[rmin[1]] = ans[lmax[1]] = 2
            print(*ans)
        else:
            index = list(range(m))
            index.sort(key=lambda i: lr[i][0]*10001000 - lr[i][1])
            M = (-INF,None)
            for i in range(m):
                l,r = lr[index[i]]
                # print(l,r)
                if r<=M[0]:
                    # 包含関係
                    print(2)
                    ans[index[i]] = 2
                    ans[M[1]] = 1
                    print(*ans)
                    break
                if r>M[0]:
                    M = (r,index[i])
            else:
                if lr[index[0]][0]==1 and lr[M[1]][1]==n:
                    print(2)
                    ans[index[0]] = ans[M[1]] = 1
                    print(*ans)
                else:
                    if m<=2:
                        print(-1)
                    else:
                        print(3)
                        ans[index[0]] = ans[index[-1]] = 2
                        ans[index[1]] = 1
                        print(*ans)
main(n,m,lr)

Ruby solution:
n,m=gets.split.map(&:to_i)
lri=m.times.map.with_index{|i|gets.split.map(&:to_i)+[i]}.sort
a=[0]*m

lri.each do |l,r,i|
  if l==1&&r==n
    puts 1
    a[i]=1
    puts a.join(" ")
    exit
  end
end

1.upto(m-1) do |j|
  l0,r0,i0=lri[j-1]
  l1,r1,i1=lri[j]
  if l0<=l1&&r1<=r0
    puts 2
    a[i0]=1
    a[i1]=2
    puts a.join(" ")
    exit
  end
end

l0,r0,i0=lri.min_by{|l,r,i|r}
l1,r1,i1=lri.max_by{|l,r,i|l}
# p [l0,r0,i0,l1,r1,i1]
if r0<l1
  puts 2
  a[i0]=2
  a[i1]=2
  puts a.join(" ")
  exit
end

l0,r0,i0=lri.min_by{|l,r,i|l}
l1,r1,i1=lri.max_by{|l,r,i|r}
# p [l0,r0,i0,l1,r1,i1]
if l0==1&&r1==n&&l1<=r0
  puts 2
  a[i0]=1
  a[i1]=1
  puts a.join(" ")
  exit
end


if m<=2
  puts -1
  exit
end

# p lri
l,r,i=lri[0,3].transpose
# p l
# p r
# p i
l=l.map{|x|x-1}
r=r.map{|x|x-1}
[1,2].repeated_permutation(3) do |b|
  c=[false]*n
  3.times do |j|
    if b[j]==1
      c[l[j]..r[j]]=[true]*(r[j]-l[j]+1)
    else
      c[0..(l[j]-1)]=[true]*l[j] if l[j]>0
      c[(r[j]+1)..(n-1)]=[true]*(n-r[j]-1) if r[j]<n-1
    end
  end
  if c.all?
    puts 3
    3.times do |j|
      a[i[j]]=b[j]
    end
    puts a.join(" ")
    exit
  end
end