package main

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

type FastScanner struct {
	data []byte
	idx  int
	n    int
}

func NewFastScanner() *FastScanner {
	data, _ := io.ReadAll(os.Stdin)
	return &FastScanner{data: data, n: len(data)}
}

func (fs *FastScanner) NextInt() int {
	for fs.idx < fs.n {
		c := fs.data[fs.idx]
		if (c >= '0' && c <= '9') || c == '-' {
			break
		}
		fs.idx++
	}
	sign := 1
	if fs.idx < fs.n && fs.data[fs.idx] == '-' {
		sign = -1
		fs.idx++
	}
	val := 0
	for fs.idx < fs.n {
		c := fs.data[fs.idx]
		if c < '0' || c > '9' {
			break
		}
		val = val*10 + int(c-'0')
		fs.idx++
	}
	return sign * val
}

func main() {
	fs := NewFastScanner()
	n := fs.NextInt()
	m := fs.NextInt()

	du := make([]int, m)
	dv := make([]int, m)
	for i := 0; i < m; i++ {
		du[i] = fs.NextInt()
		dv[i] = fs.NextInt()
	}

	e := n + m
	from := make([]int, 2*e)
	to := make([]int, 2*e)
	rev := make([]int, 2*e)
	nxt := make([]int, 2*e)
	face := make([]int, 2*e)
	for i := range face {
		face[i] = -1
	}

	adjHalf := make([][]int, n+1)
	ec := 0
	addEdge := func(u, v int) {
		h := 2 * ec
		from[h] = u
		to[h] = v
		rev[h] = h + 1
		from[h+1] = v
		to[h+1] = u
		rev[h+1] = h
		adjHalf[u] = append(adjHalf[u], h)
		adjHalf[v] = append(adjHalf[v], h+1)
		ec++
	}

	for i := 1; i < n; i++ {
		addEdge(i, i+1)
	}
	addEdge(n, 1)
	for i := 0; i < m; i++ {
		addEdge(du[i], dv[i])
	}

	for v := 1; v <= n; v++ {
		list := adjHalf[v]
		vv := v
		sort.Slice(list, func(i, j int) bool {
			a := to[list[i]] - vv
			if a <= 0 {
				a += n
			}
			b := to[list[j]] - vv
			if b <= 0 {
				b += n
			}
			return a < b
		})
		adjHalf[v] = list
		d := len(list)
		for i, hout := range list {
			hin := rev[hout]
			nxt[hin] = list[(i-1+d)%d]
		}
	}

	faces := make([][]int, 0, m+2)
	for h := 0; h < 2*e; h++ {
		if face[h] != -1 {
			continue
		}
		cur := h
		verts := make([]int, 0)
		for {
			face[cur] = len(faces)
			verts = append(verts, from[cur])
			cur = nxt[cur]
			if cur == h {
				break
			}
		}
		faces = append(faces, verts)
	}

	outerFace := face[1]
	k := m + 1

	regOfFace := make([]int, len(faces))
	for i := range regOfFace {
		regOfFace[i] = -1
	}

	rotateMin := func(vs []int) []int {
		s := len(vs)
		pos := 0
		for i := 1; i < s; i++ {
			if vs[i] < vs[pos] {
				pos = i
			}
		}
		out := make([]int, s)
		copy(out, vs[pos:])
		copy(out[s-pos:], vs[:pos])
		return out
	}

	regions := make([][]int, 0, k)
	for fid, verts := range faces {
		if fid == outerFace {
			continue
		}
		regOfFace[fid] = len(regions)
		regions = append(regions, rotateMin(verts))
	}

	dual := make([][]int, k)
	for id := n; id < e; id++ {
		r1 := regOfFace[face[2*id]]
		r2 := regOfFace[face[2*id+1]]
		dual[r1] = append(dual[r1], r2)
		dual[r2] = append(dual[r2], r1)
	}

	orderIdx := make([]int, k)
	for i := 0; i < k; i++ {
		orderIdx[i] = i
	}
	sort.Slice(orderIdx, func(i, j int) bool {
		a := regions[orderIdx[i]]
		b := regions[orderIdx[j]]
		p := len(a) - 1
		q := len(b) - 1
		for p >= 0 && q >= 0 {
			if a[p] != b[q] {
				return a[p] < b[q]
			}
			p--
			q--
		}
		return len(a) < len(b)
	})

	removed := make([]bool, k)
	color := make([]int, k)
	parent := make([]int, k)
	size := make([]int, k)

	var decompose func(int, int)
	decompose = func(start, depth int) {
		stack := []int{start}
		order := make([]int, 0)
		parent[start] = -1

		for len(stack) > 0 {
			v := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			order = append(order, v)
			for _, w := range dual[v] {
				if removed[w] || w == parent[v] {
					continue
				}
				parent[w] = v
				stack = append(stack, w)
			}
		}

		total := len(order)
		for i := total - 1; i >= 0; i-- {
			v := order[i]
			size[v] = 1
			for _, w := range dual[v] {
				if removed[w] || parent[w] != v {
					continue
				}
				size[v] += size[w]
			}
		}

		best := total + 1
		cent := -1
		for _, v := range order {
			mx := total - size[v]
			for _, w := range dual[v] {
				if removed[w] || parent[w] != v {
					continue
				}
				if size[w] > mx {
					mx = size[w]
				}
			}
			if mx < best {
				best = mx
				cent = v
			}
		}

		color[cent] = depth + 1
		removed[cent] = true
		for _, w := range dual[cent] {
			if !removed[w] {
				decompose(w, depth+1)
			}
		}
	}

	decompose(0, 0)

	ans := make([]int, k)
	for i, r := range orderIdx {
		ans[i] = color[r]
	}

	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	buf := make([]byte, 0, 4*k)
	for i, x := range ans {
		if i > 0 {
			buf = append(buf, ' ')
		}
		buf = strconv.AppendInt(buf, int64(x), 10)
	}
	buf = append(buf, '\n')
	out.Write(buf)
	out.Flush()
}