P10006

P1006 二分图判定

Description

给出一个 \(n\) 个点，\(m\) 条边的无向图，你需要判断它是否是一个二分图。

Format

Input

本题有共有 \(T\) 组数据，第一行输入整数 \(T\)，对于每组数据，输入格式为：

第一行输入两个正整数 \(n,m\)。

接下来 \(m\) 行每行输入两个正整数 \(x,y\) 表示 \(x\) 到 \(y\) 有一条边。

本题共有 \(3\) 个测试点包。

对于测试点包 \(1\)，满足 \(n\le 10,m\le 20,T\le 10\)，共 \(20\) 分。

对于测试点包 \(2\)，满足 \(n\le 1000,m\le 2000,T\le 10\)，共 \(30\) 分。

对于测试点包 \(3\)，保证 \(1\le n\le 4\times 10^5,1\le m\le 8\times 10^5,1\le \sum n\le 10^6,1\le \sum m\le 2\times 10^6\)，共 \(50\) 分。保证所有操作满足题目描述，保证每一行的两个相邻整数都仅用一个空格隔开。

Output

对于每组数据，输出单独一行表示结果，如果是二分图，输入 "Y"，否则输出 "N"，不带引号。

Samples

Sample Input 1

3
5 5
1 2
1 3
1 4
1 5
2 3
6 7
1 4
2 5
3 6
1 4
1 5
3 4
4 3
1 2
1 1
1 1

Sample Output 1

N
Y
N