{"raw_statement":[{"iden":"statement","content":"Как гласят старые малоярославские легенды, где-то далеко-далеко, где сборная России когда-то готовилась к международной олимпиаде, в одной из общеобразовательных школ живёт Граф. Ориентированность Графа, как следует из легенд, меняется от дня ко дню вместе с количеством вершин и ребер, что позволяет Графине и её отражению не скучать и играть во множество игр на Графе.\n\nВот уже многие дни Граф обрёл постоянную ориентированность; однако в последнее время Граф часто стал бывать раздражительным и колючим, и для Графини настали нелёгкие дни. Чтобы хоть как-то облегчить себе жизнь, Графиня решила написать программу, которая по текущему состоянию, то есть набору вершин и рёбер, сообщит Графине, является ли граф колючим. По опыту прошлых дней, Графиня заключила, что Граф является колючим, если и только если через любое его ребро проходит не более чем один простой цикл.\n\nНапомним, что последовательность ребер (u1, u2), (u2, u3), ..., (uk - 1, uk), (uk, u1) является простым циклом, если вершины u1, u2, ..., uk попарно различны. Простой цикл проходит через ребро e, если ребро e содержится в последовательности ребер цикла.\n\nПетлёй в графе называется ребро (u, v), т.ч. u = v.\n\nРёбра (u1, v1) и (u2, v2) называются кратными, если u1 = u2 и v1 = v2.\n\nПомогите Графине понять, является ли её Граф, являющийся *ориентированным* графом без петель и кратных ребер, колючим или нет.\n\nВ первой строке записаны целые неотрицательные числа n и m (1 ≤ n ≤ 500 000, 0 ≤ m ≤ 106 - количество вершин и рёбер графа-Графа.\n\nДалее в следующих m строках записано по паре целых чисел u, v, 1 ≤ u, v ≤ n, u ≠ v.\n\nГарантируется, что в Графе не существует петель и кратных ребер.\n\nВыведите слово \"_YES_\", если Граф является колючим, и \"_NO_\" иначе.\n\n"},{"iden":"входные данные","content":"В первой строке записаны целые неотрицательные числа n и m (1 ≤ n ≤ 500 000, 0 ≤ m ≤ 106 - количество вершин и рёбер графа-Графа.Далее в следующих m строках записано по паре целых чисел u, v, 1 ≤ u, v ≤ n, u ≠ v.Гарантируется, что в Графе не существует петель и кратных ребер."},{"iden":"выходные данные","content":"Выведите слово \"_YES_\", если Граф является колючим, и \"_NO_\" иначе."},{"iden":"примеры","content":"Входные данные3 31 22 33 1Выходные данныеYESВходные данные3 41 22 33 11 3Выходные данныеNO"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ G = (V, E) $ be a directed graph with $ |V| = n $, $ |E| = m $, containing no self-loops or multiple edges.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 500{,}000 $  \n2. $ 0 \\leq m \\leq 10^6 $  \n3. All edges $ (u, v) \\in E $ satisfy $ u \\neq v $, and no two edges are identical.\n\n**Objective**  \nDetermine whether $ G $ is *spiky*:  \nFor every edge $ e \\in E $, there is **at most one** simple directed cycle in $ G $ that contains $ e $.  \n\nOutput \"YES\" if $ G $ is spiky; \"NO\" otherwise.","simple_statement":"Given a directed graph with n vertices and m edges (no self-loops, no multiple edges), determine if it is \"spiky\": every edge belongs to at most one simple cycle. Print \"YES\" if spiky, \"NO\" otherwise.","has_page_source":false}