Time Limit: 1000 MS              Memory Limit: 256 M


给出一幅n个点,m条边的图,分别判断该图是无向图和有向图条件下,是否存在欧拉通路。

输入

输入包含多组数据。第一行为一个整数T(1 ≤ T ≤ 100),代表数据组数,对于每组数据: 第一行是两个整数n和m( 1 ≤ n ≤ 500, 0 ≤ m ≤ n(n − 1)/2 ),分别代表图上点的个数和边的个数。
然后是m行,每行两个整数uivi ( 1 ≤ ui, vi ≤ n, ui ≠ vi ),代表图上的一条边所连接的两个点。输入保证没有重边。

输出

首先判断:如果这幅图是无向图,是否存在欧拉通路;
其次判断:如果这幅图是有向图,是否存在欧拉通路。
对于每个判断,如果存在,输出"Yes",否则输出"No"(不包括引号)。两个判断间用空格隔开。

样例输入

3

2 1
1 2

4 3
1 2
1 3
1 4

4 4
1 2
1 3
1 4
2 3

样例输出

Yes Yes
No No
Yes No

Hint

欧拉通路、欧拉回路、欧拉图
无向图
1) 设 G 是连通无向图,则称经过 G 的每条边一次并且仅一次的路径为欧拉通路;
2) 如果欧拉通路是回路 (起点和终点是同一个顶点), 则称此回路为欧拉回路 (Euler circuit);
3) 具有欧拉回路的无向图 G 称为欧拉图(Euler graph)。
有向图
1) 设 D 是有向图, D 的基图连通,则称经过 D 的每条边一次并且仅一次的有向路径为有向欧拉通路;
2) 如果有向欧拉通路是有向回路,则称此有向回路为有向欧拉回路(directed Euler circuit);
3) 具有有向欧拉回路的有向图 D 称为有向欧拉图(directed Euler graph)。

Extend

欧拉回路打印路径算法:Fleury(佛罗莱)算法

Author

GooZy