All Tracks Algorithms Graphs Graph Representation Problem

"2" Way Attack
Tag(s):

Medium

Problem
Editorial
Analytics

The blue army is on the move for the attack on red army.There are infinite number of infinite types of bombs numbered 1,2.... available with blue army to destroy the base camp of the red army.The general of the blue army wants the destruction of the area quick. General ordered his secret services to produce the blue print of the area and necessary details for the attack to take place without any problem.The blue print generated gave the following information: The red army base camp has N tents connected by M gas lines,containing a special gas which prevents explosion to some extent.Each tent has to be targeted with a bomb of some type. General also got a surprising intelligence that the base is designed in such a way that if a gas pipe connects two tents ,then these two tents cannot be bombed with bombs who's type differ by greater than or equal to 2.Also if there is no gas pipe connecting any pair of tents then they have to be bombed with bomb types who's type differ by greater than equal to 2.All this made the task of the general complicated.The general also wants minimum number of his bombs to be used for destruction.Help the general in bombing the blue army in minimum number of types of bombs required. If the base camp is designed in such a way it cannot be bombed print "NO"(without quotes).

Input:

The First line of input consists of T, the number of test cases. The next line has two integers N and M indicating number of tents and gas lines. The next M lines have two integers U and V indicating a gas line between tents U and V.

Output:

For each print "YES"(without quotes) in first line if bombing is possible and then minimum number of bombs required. Else print "NO"(without quotes) if the base is indestructible.

Constraints:

1<=T<=3

1<=N,M,U,V<=100000

 

SAMPLE INPUT
2
3 2
1 2
2 3
4 4
1 2
2 3
3 4
4 1
SAMPLE OUTPUT
YES
3
NO
Explanation

None

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), TypeScript, Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

NIT Surat

Challenge Name

EPIPHANY 7.1

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?