#! /usr/bin/env python

from sys import stdin, stderr, argv
from collections import defaultdict
from random import randint

OPEN = 0
CLOSE = 1

class Event:
    def __init__(self, pos, type, id):
        self.pos = pos
        self.type = type
        self.id = id

    def __repr__(self):
        return '%s%d@%d' % ('[' if self.type == OPEN else ']', self.id, self.pos)

def main():
    intervals = []
    k = int(argv[1])

    if len(argv) <= 2:
        for line in stdin:
            l, r = line.split()
            l = float(l)
            r = float(r)
            intervals.append((l, r))
    else:
        for i in range(int(argv[2])):
            while True:
                l = randint(0, 99999)
                r = randint(0, 99999)
                if l < r:
                    break
            intervals.append((l, r))

    print >> stderr, "calculating events..."
    events = []
    for i in range(len(intervals)):
        l, r = intervals[i]
        events.append(Event(l, OPEN, i))
        events.append(Event(r, CLOSE, i))

    print >> stderr, "sorting events..."
    evs = sorted(events, key=lambda e: e.pos)

    print >> stderr, "discoinciding events..."
    d = 0
    last = -1
    for i in range(len(evs)):
        p = evs[i].pos
        p += d
        if p <= last:
            p += last - p + 1
            d += last - p + 1
        evs[i].pos = p
        last = p

    print >> stderr, "creating constraints..."
    active = []
    next = len(intervals)
    constraints = []
    for e in evs:
        if not active:
            active = [e.id]
            active_type = e.type
        else:
            if active_type == e.type:
                if len(active) + 1 < k:
                    active.append(e.id)
                else:
                    constraints.append((active_type, active + [e.id]))
                    active = []
            else:
                xs = range(next, next + (k - len(active)))
                next += len(xs)
                constraints.append((active_type, active + xs))
                ys = range(next, next + (k - len(xs) - 1))
                next += len(ys)
                constraints.append((CLOSE if active_type == OPEN else OPEN, xs + [e.id] + ys))
                active = ys
    print >> stderr, "%d constraints, %d variables" % (len(constraints), next)

    print >> stderr, "calculating occurrences..."
    occur = defaultdict(set)
    for i in range(len(constraints)):
        _, c = constraints[i]
        for id in c:
            occur[id].add(i)

    print >> stderr, "calculating graph..."
    g = defaultdict(list)
    for edge, [x, y] in occur.iteritems():
        g[x].append((y, edge))
        g[y].append((x, edge))

    print >> stderr, "verifying bipartiteness..."
    for u in g:
        cu, _ = constraints[u]
        for (v, _) in g[u]:
            cv, _ = constraints[v]
            if cu == cv:
                print >> stderr, "internal error: graph not bipartite"
                exit(1)

    print >> stderr, "solving edge coloring problem..."
    coloring = defaultdict(lambda: None)
    uncolored = set(range(next))
    colors = set(range(k))
    while uncolored:
        e = uncolored.pop()
        u, v = occur[e]
        c_u = colors - set([coloring[ee] for (x, ee) in g[u]])
        c_v = colors - set([coloring[ee] for (x, ee) in g[v]])
        cu = c_u.pop()
        cv = c_v.pop()
        c = cv
        path = []
        while True:
            for (nu, eu) in g[u]:
                if coloring[eu] == c:
                    u = nu
                    path.append(eu)
                    c = cu if c == cv else cv
                    break
            else:
                break
        for edge in path:
            coloring[edge] = cu if coloring[edge] == cv else cv
        coloring[e] = cv

    print >> stderr, "verify edge coloring..."
    for u in g:
        cs = set()
        for (_, eu) in g[u]:
            cs.add(coloring[eu])
        assert(cs == colors)

    if len(argv) <= 2:
        def s(x):
            if x == int(x):
                return str(int(x))
            else:
                return str(x)

        for i in range(len(intervals)):
            l, r = intervals[i]
            print s(l), s(r), coloring[i]

    print >> stderr, "verifying..."

    counts = [0] * k
    max_d = 0
    for ev in events:
        max_d = max(max_d, abs(max(counts) - min(counts)))
        if ev.type == OPEN:
            counts[coloring[ev.id]] += 1
        else:
            counts[coloring[ev.id]] -= 1
    if max_d > 1:
        print >> stderr, "internal error: max_d =", max_d
        exit(1)

main()