import scala.annotation.tailrec
import scala.collection.mutable
import scala.collection.mutable.ArrayBuffer
import scala.io.StdIn._
object Main extends App {
  solve()
  @tailrec def solve(): Unit = {
    val Array(n, m) = readLine.trim.split(' ').map(_.toInt)
    if (n == 0) return
    val relations = Array.tabulate(m){_ ⇒
      val Array(u, v) = readLine.trim.split(' ').map(_.toInt - 1)
      (u, v)
    }
    val (min, max) = pushFlow(makeNetwork(relations, n), n, m, n + m)
    println(s"$min $max")
    solve()
  }
  case class Edge(to: Int, pair: Int, var flow: Int)
  def pushFlow(nodes: Array[ArrayBuffer[Edge]], person: Int, relation: Int, goal: Int): (Int, Int) = {
    val prev = Array.fill(nodes.length){Nil: List[Edge]}
    for (from ← person until person + relation) {
      var maxFlow = 0
      prev.indices.foreach(i ⇒ prev(i) = Nil)
      val queue = mutable.Queue(from)
      while (queue.nonEmpty) {
        val current = queue.dequeue()
        for (next ← nodes(current) if next.flow > 0) {
          if (next.to == goal) {
            if (next.flow > maxFlow) {
              maxFlow = next.flow
              prev(goal) = next::prev(current)
            }
          }else if (prev(next.to).isEmpty) {
            prev(next.to) = next::prev(current)
            queue.enqueue(next.to)
          }
        }
      }
      for (e ← prev(goal)) {
        e.flow -= 1
        nodes(e.to)(e.pair).flow += 1
      }
    }
    val sorted = nodes(goal).sortBy(_.flow)
    (sorted.head.flow, sorted.last.flow)
  }
  def makeNetwork(relations: Array[(Int, Int)], personCount: Int): Array[ArrayBuffer[Edge]] = {
    val result = Array.fill(personCount + relations.length + 1){ArrayBuffer[Edge]()}
    val goal = result.length - 1
    for (p ← 0 until personCount) {
      result(p).append(Edge(goal, result(goal).length, relations.length))
      result(goal).append(Edge(p, 0, 0))
    }
    for (r ← relations.indices) {
      val (a, b) = relations(r)
      result(r + personCount).append(Edge(a, result(a).length, 1))
      result(a).append(Edge(r + personCount, result(r + personCount).length - 1, 0))
      result(r + personCount).append(Edge(b, result(b).length, 1))
      result(b).append(Edge(r + personCount, result(r + personCount).length - 1, 0))
    }
    result
  }
}

