Задача №113507. Экспедиция
Винни-Пух отправился в очередную Экспедицию по Лесу!
Лес представляет собой n полянок, соединённых m двусторонними тропинками. При этом возможно, что для некоторых полянок не существует способа добраться из одной в другую по тропинкам. За половину суток (день или ночь) Пух проходит ровно по одной тропинке.
Когда Пух пришёл на рассвете на очередную полянку, ему показалось, что он вернулся к полянке, с которой он начал свое путешествие. Он также уверен, что не проходил ни по одной тропинке дважды, и что все полянки до этого были различными. Также он помнит, что он отправился в Экспедицию на рассвете, то есть число дней в пути было равно числу ночей.
Вы решили помочь медвежонку и хотите определить по карте Леса, могло ли такое случиться.
Первая строка содержит число T — число наборов входных данных, которые вам предстоит обработать. Далее следуют T наборов входных данных. Каждый набор задаётся в следующем формате.
В первой строке набора входных данных заданы два числа n и m ( 2 ≤ n ≤ 500 000 , 1 ≤ m ≤ 500 000 ) — количество полянок и количество тропинок в соответствующем Лесу.
В следующих m строках содержатся описания тропинок: каждая строка состоит из двух целых чисел u i , v i ( 1 ≤ u i , v i ≤ n , u i ≠ v i ), обозначающих номера полянок, соединённых очередной тропинкой.
Гарантируется, что никакие две полянки не соединены двумя или более тропинками.
Гарантируется, что и суммарное число полянок, и суммарное число тропинок по всем наборам входных данных не превзойдёт 500 000 .
Для каждого набора входных данных выведите в отдельной строке " YES ", если в Лесу существует маршрут, удовлетворяющий описанию Пуха, и " NO " в противном случае.
Тест из условия состоит из двух наборов входных данных.
В первом примере Пух мог начать Экспедицию на полянке с номером 2 , в первый день перейти на полянку 5 , в первую ночь перейти на полянку 3 , во второй день перейти на полянку 4 и во вторую ночь вернуться обратно на полянку 2 .
Во втором примере, независимо от выбора начальной полянки, Пух может вернуться на неё, но ему в любом случае потребуется три перехода, а значит дней в пути будет больше, чем ночей.
2 5 6 1 2 2 3 3 4 4 5 5 2 5 3 3 3 1 2 2 3 3 1
YES NO