← 返回题目列表

Codeforces · 1239/D

D. 卡托维兹市

中文机器翻译题面 查看原题

下周末将在卡托维兹市举行猫咪大赛。不过,评审团成员和参赛者尚未选定。卡托维兹有 $$$n$$$ 居民和 $$$n$$$ 猫,并且每个居民的房子里都住着一只猫。居民和猫用从 $$$1$$$ 到 $$$n$$$ 的整数进行编号,其中第 $$$i$$$ 只猫住在第 $$$i$$$ 居民的房子里。

每个卡托维兹居民都与几只猫保持着友谊,其中包括住在他家里的那只猫。为了进行比赛,至少需要一名评委,并且至少需要一名猫参赛者。当然,每个评审团成员都不应该认识任何参赛者。为了使比赛取得成功,评委会成员人数加上参赛者人数还需要等于$$$n$$$。

请帮助卡托维兹居民为即将举行的比赛选择评审团和参赛者,或者确定这是不可能的。

输入

第一行包含一个整数$$$t$$$ ($$$1 \le t \le 100\,000$$$),测试用例的数量。然后是$$$t$$$测试用例的描述,其中每个描述如下:

第一行包含整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le m \le 10^6$$$)、卡托维兹居民的数量以及居民和猫之间的友谊对的数量。

接下来的 $$$m$$$ 行包含整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$),表示第 $$$a_i$$$ 居民与第 $$$b_i$$$ 猫相识。保证每对某位居民和某只猫最多列出一次。

可以保证,对于每一个 $$$i$$$,第 $$$i$$$ 个居民和第 $$$i$$$ 个猫之间都存在一对。

不同的测试用例用空行分隔。

保证所有测试用例的 $$$n$$$ 总和最多为 $$$10^6$$$,并且所有测试用例的 $$$m$$$ 总和最多为 $$$10^6$$$。

输出

对于每个测试用例打印:

- 如果无法选择评审团和参赛者,则选择“否”。
- 否则打印“Yes”。在第二行中打印两个整数 $$$j$$$ 和 $$$p$$$ ($$$1 \le j$$$, $$$1 \le p$$$, $$$j + p = n$$$) — 评审团成员的数量和竞赛参与者的数量。在第三行中打印 $$$j$$$ 从 $$$1$$$ 到 $$$j$$$ 的不同整数$$$n$$$,组成陪审团的居民的索引。在第四行中打印 $$$p$$$ 从 $$$1$$$ 到 $$$n$$$ 的不同整数,将参加比赛的猫的索引。如果有多个正确答案,请打印其中任何一个。

示例

输入 #1

4
3 4
1 1
2 2
3 3
1 3

3 7
1 1
1 2
1 3
2 2
3 1
3 2
3 3

1 1
1 1

2 4
1 1
1 2
2 1
2 2

输出 #1

Yes
2 1
1 3 
2 
Yes
1 2
2 
1 3 
No
No

注意

在第一个测试案例中,我们可以选择第一和第三位居民作为陪审团。他们俩都不认识第二只猫,所以我们可以选择它作为参赛者。

在第二个测试案例中,我们可以选择第二位居民作为陪审团。他与第一只猫和第三只猫不是熟人,因此可以选择它们作为参赛者。

在第三个测试用例中,唯一的居民是唯一的猫的熟人,因此他们不能一起参加比赛。因此,不可能在至少有一名陪审团和至少一只猫的情况下进行比赛。

在第四个测试案例中,每个居民都熟悉每只猫,因此再次不可能与至少一个陪审团和至少一只猫进行比赛。