CF1239D Catowice City

在 Catowice 城市，下周末将举办一场猫咪比赛。然而，评委和参赛猫尚未选定。Catowice 有 $n$ 位居民和 $n$ 只猫，每位居民家中恰好养着一只猫。居民和猫的编号均为 $1$ 到 $n$，其中第 $i$ 只猫住在第 $i$ 位居民家中。 每位居民都与若干只猫是朋友关系，包括他家中的那只猫。为了举办比赛，至少需要一名评委和至少一只参赛猫。当然，每位评委都不能认识任何一只参赛猫。为了比赛顺利进行，还要求评委人数与参赛猫数量之和等于 $n$。 请帮助 Catowice 的居民选出评委和参赛猫，或者判断是否无法做到。

第一行包含一个整数 $t$（$1 \le t \le 100\,000$），表示测试用例的数量。接下来是 $t$ 个测试用例的描述，每个测试用例格式如下： 第一行包含两个整数 $n$ 和 $m$（$1 \le n \le m \le 10^6$），分别表示 Catowice 的居民数和居民与猫之间的友谊对数。 接下来的 $m$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le n$），表示第 $a_i$ 位居民与第 $b_i$ 只猫是朋友。保证每对居民与猫的组合最多出现一次。 保证对于每个 $i$，都存在一对 $(i, i)$，即第 $i$ 位居民与第 $i$ 只猫是朋友。 不同测试用例之间用一个空行隔开。 保证所有测试用例中 $n$ 的总和不超过 $10^6$，$m$ 的总和也不超过 $10^6$。

对于每个测试用例，输出： - 如果无法选出评委和参赛猫，输出“No”。 - 否则，输出“Yes”。第二行输出两个整数 $j$ 和 $p$（$1 \le j$，$1 \le p$，$j + p = n$），分别表示评委人数和参赛猫数量。 - 第三行输出 $j$ 个不同的 $1$ 到 $n$ 之间的整数，表示组成评委的居民编号。 - 第四行输出 $p$ 个不同的 $1$ 到 $n$ 之间的整数，表示参赛的猫的编号。 如果有多组合法答案，可以输出任意一组。

在第一个测试用例中，可以选择第 1 位和第 3 位居民作为评委，他们都不认识第 2 只猫，因此可以选择第 2 只猫作为参赛猫。 在第二个测试用例中，可以选择第 2 位居民作为评委，他不认识第 1 只和第 3 只猫，因此可以选择这两只猫作为参赛猫。 在第三个测试用例中，唯一的居民与唯一的猫是朋友，因此无法同时选出至少一名评委和一只参赛猫。 在第四个测试用例中，每位居民都与每只猫是朋友，因此同样无法选出至少一名评委和一只参赛猫。 由 ChatGPT 4.1 翻译