Server Time: Wed Feb 26, 2020 12:48 pm
Welcome ( logout
D - Game of Connect
PDF (English) Ranklist
Time Limit: 3 second(s) Memory Limit: 32 MB

In the Game of connect two players are given a graph with n vertices and m edges. Before starting the game the first player selects two distinct vertices A and B. The goal of the second player is to connect A and B with a sequence of colored edges. Initially all the edges are uncolored. In his move first player can select an uncolored edge and deletes it from the graph. In his move second player can select an uncolored edge and colors it. If second player can connect A and B with a sequence of colored edges then he wins. Otherwise the first player wins. Players take their move by turns and the first player always goes first. Given a graph you need to determine whether second player has a winning strategy or not. Assume that both of the players play perfectly.

 

Input

First line of the input contains T (T ≤ 100) the number of test cases. Each test case starts with a line containing n (2 ≤ n ≤ 100) and m (1 ≤ m ≤ 300). Each of the next m lines contains two integers u and v denoting an edge between u and v. The vertices are numbered from 0 to n-1. There will not be any duplicate edge.

 

Output

For each test case produce one line of output. This line contains the serial of output followed by a string “YES” if the second player has a winning strategy and “NO” otherwise (without the quotes). Look at the output for sample input for details.

 

Sample Input                              Output for Sample Input

2

4 6

0 1

0 2

0 3

1 2

1 3

2 3

4 4

0 1

1 2

2 3

3 0

 

Case 1: YES

Case 2: NO

 


 


Problem Setter: Abdullah Al Mahmud
Special Thanks: Md. Mahbubul Hasan
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan