object Main {

  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)
    val V, E = sc.nextInt()
    val X = new Array[Int](E)
    val Y = new Array[Int](E)
    (0 until E) foreach { i =>
      val x, y = sc.nextInt()
      X(i) = x - 1
      Y(i) = y - 1
    }

    allPointsPairBellmanFord(X, Y)(E, V) match {
      case Some(result) =>
        println(result.flatMap(_.filter {
          case DISTANCE_INF => false
          case _ => true
        }).max)
      case None =>
        println("NEGATIVE CYCLE")
    }
  }

  final private[this] def bellmanFord(
                                       X: Array[Int],
                                       Y: Array[Int],
                                       start: Int
                                     )(E: Int, V: Int): Option[IndexedSeq[Long]] = {
    val distance = Array.fill[Long](V)(DISTANCE_INF)
    val parents = Array.fill(V)(PARENT_UNDEFINED)
    distance(start) = 0

    def relax(u: Int, v: Int): Unit =
      if (distance(u) != DISTANCE_INF &&
        distance(v) < distance(u) + 1) {
        distance(v) = distance(u) + 1
        parents(v) = u
      }

    var i = 0
    while (i < V - 1) {
      var j = 0
      while (j < E) {
        relax(X(j), Y(j))
        j += 1
      }
      i += 1
    }

    i = 0
    while (i < E) {
      if (distance(X(i)) != DISTANCE_INF &&
        distance(Y(i)) < distance(X(i)) + 1)
        return None
      i += 1
    }
    Some(distance)
  }

  final private[this] def allPointsPairBellmanFord(
                                                    X: Array[Int],
                                                    Y: Array[Int]
                                                  )(E: Int, V: Int): Option[IndexedSeq[IndexedSeq[Long]]] = {
    import scala.collection.mutable
    (0 until V). foldLeft (Option(mutable.ArrayBuilder.make[IndexedSeq[Long]]())) { case (reduced, next) =>
      reduced match {
        case Some(builder) => bellmanFord(X, Y, next)(E, V) map builder.+=
        case None => None
      }
    } map (_.result())
  }

  final private[this] val DISTANCE_INF = Long.MinValue / 2
  final private[this] val PARENT_UNDEFINED = -1

}
