#include <iostream>
#include <cstdio>
#include <algorithm>                 

using namespace std;

const int NMAX=100, KMAX=100, GAP=30;

struct Request{
  int t1, t2, order;
  bool operator < (const Request &r) const{
    return t2<r.t2 || t2==r.t2 && t1<r.t1;
  }
};

int rooms[NMAX]; //во сколько может начаться очередное мероприятие
Request reqs[KMAX];
int ans[KMAX+1]; //ответы - какая заявка в какой зал пойдёт
int n,k,req_count,max_room;

int main() {
//  freopen("rest.in", "r", stdin);
//  freopen("rest.out", "w", stdout);

  scanf("%d %d", &n, &k);
  for (int i=0; i<k; i++) {
    int h1, m1, h2, m2;
    scanf("%d:%d-%d:%d", &h1, &m1, &h2, &m2);
    reqs[i].t1 = h1*60+m1;
    reqs[i].t2 = h2*60+m2;
    reqs[i].order = i+1;
  }
  sort(reqs,reqs+k);
  for (int i=0; i<k; i++) {
    int room=-1;
    for (int j=0; j<n; j++)
      if (rooms[j]<=reqs[i].t1)
        if (room==-1 || rooms[room]<rooms[j])
          room=j;
    if (room>=0) {
      ans[reqs[i].order] = room+1;
      req_count++;
      rooms[room] = reqs[i].t2 + GAP;
      if (max_room<room) max_room=room;
    }
  }
  cout << req_count << " " << max_room+1 << endl;
  for (int i=1; i<=k; i++)
    if (ans[i]>0) 
      cout << i << " " << ans[i] << endl;

  return 0;
}
