1006. 今晚吃流年

题目描述

又是一年秋天，飘落的银杏树叶在地上堆成金色的小山。看着学生们用银杏叶在地上摆成的图案，你不禁想起……

这是一个有 $n$ 个学生的班级，同学们的学号为 $1,2,3,\cdots,n$。你知道班里的同学们有的时候会“磕 CP”，也就是选择两名异性的学号组在一起，可以是男生的学号在前，也可以是女生的学号在前。

你知道性别和学号是以如下方式对应的：存在整数数对 $\lparen a_1,a_2\rparen$（$1<a_1<a_2<n + 1$），使得 $1, 2,\cdots,a_1 - 1$ 号以及 $a_2,a_2+1,\cdots,n$ 号为一个性别，$a_1,a_1+1,\cdots,a_2 - 1$ 号为另一个性别。

现在你从同学们口中听到了 $m$ 对学号。假如他们都在“磕 CP”，那么是否存在满足男女性别条件的数对呢？

输入格式

本题包含多组测试数据。

首先在第一行输入一个整数 $T$（$1\le T\le 30$）表示测试数据组数。

接下来对于每一组测试数据：

第一行包含两个整数 $n,m$（$3\le n \le 2 \times 10^5$，$\sum n\le 5\times 10^5$，$1\le m\le 2\times10^5$，$\sum m \le 5 \times 10^5$），表示学生的数量与 CP 的数量。

接下来 $m$ 行，第 $i+1$（$1\le i\le m$）行包含两个整数 $c_i,p_i$（$1\le c_i,p_i\le n$，$c_i\not=p_i$），表示第 $i$ 组 CP 对应的两个学号。不保证 $c_i, p_i$ 两两不同。

输出格式

本题启用 Special Judge 评测。

对于每一组测试数据，若存在满足条件的数对 $\lparen a_1,a_2 \rparen$，那么首先输出一行一个字符串 Yes，并在第二行输出 $a_1, a_2$ 两个由空格隔开的正整数；否则，输出一行一个字符串 No。

若有多组满足条件的数对，输出任意一组都算作正确。

样例输入

2
3 2
1 2
2 3
3 3
1 2
2 3
3 1

样例输出

Yes
2 3
No

来源：2026杭电多校-测试专用（南外） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1235&pid=1006 ⚠ 本题为 Special Judge。官方数据中的 .out 多为评测机判定输出（如 AC/OK/Correct/yes），导入后需自行提供 checker 方可正确评测。