Задан ориентированный граф, состоящий из n вершин и m ребер (рёбра являются направленными, т. е. по каждому ребру можно проходить только в одном направлении). Разрешается удалить не более одного ребра из него.
Можно ли сделать этот граф ацикличным, совершив такую операцию? Граф называется ацикличным, если в нём не существует циклов (цикл — непустой путь, начинающийся и заканчивающийся в одной и той же вершине).
В первой строке записаны два целых числа n и m (2 ≤ n ≤ 500, 1 ≤ m ≤ min(n(n - 1), 100000)) — количество вершин и ребер, соответственно.
Затем идут m строк. В каждой записаны по два целых числа u и v, задающие ориентированное ребро из вершины u в вершину v (1 ≤ u, v ≤ n, u ≠ v). Каждая упорядоченная пара (u, v) встречается не более одного раза (существует не более одного ориентированного ребра из u в v).
Если возможно сделать граф ацикличным, удалив не более одного ребра, то выведите YES. В противном случае выведите NO.
3 4
1 2
2 3
3 2
3 1
YES
5 6
1 2
2 3
3 2
3 1
2 1
4 5
NO
В первом примере можно удалить ребро , и граф станет ацикличным.
Во втором примере необходимо удалить не менее двух ребер (например, и ), чтобы сделать граф ацикличным.
Название |
---|