一、题意理解

我们有一个 n 个点的无向图，表示好友关系（边表示互相认识）。

定义两种聚会：

1. 热闹聚会（周六）：选出任意大小的点集 S，满足：

   • 对 S 中每个点，在 S 中至少有 p 个邻居（认识的人）；
   • 至少有一个点在 S 中恰好有 p 个邻居。 这样的 p 称为热闹度，输出 S 即可。

2. 尴尬聚会（周日）：选出恰好 q 个点，它们之间两两没有边（独立集）。q 称为尴尬度。

条件： [ \left\lfloor \frac{n}{p+1} \right\rfloor \le q \quad \text{且} \quad \left\lfloor \frac{n}{q+1} \right\rfloor \le p ] 注意：不是要我们输出 p 和 q，而是输出两个点集，它们的 p 和 q 自然会满足这个不等式。

---

二、条件转化与思路

这个不等式看起来很奇怪，但它实际上是一个对称的不等式，联系着 p 和 q。
我们观察一下，如果设
[ p+1 = a, \quad q+1 = b ] 那么条件变为： [ \left\lfloor \frac{n}{a} \right\rfloor \le b-1 \quad\text{和}\quad \left\lfloor \frac{n}{b} \right\rfloor \le a-1 ] 但这样可能不直观。

其实，有一个经典结论：对于任意正整数 (p, q)，如果
[ (p+1)(q+1) > n ] 那么条件 (\lfloor n/(p+1) \rfloor \le q) 和 (\lfloor n/(q+1) \rfloor \le p) 成立。
因为 (\lfloor n/(p+1) \rfloor \le n/(p+1) \le q) 当且仅当 (n < (p+1)(q+1)) 时严格成立吗？
我们验证：
(\lfloor n/(p+1) \rfloor \le q) 等价于 (n/(p+1) < q+1)，即 (n < (p+1)(q+1))。
同理另一个也是 (n < (p+1)(q+1))。
所以两个不等式等价于： [ (p+1)(q+1) > n ]

因此，题目条件就是： [ (p+1)(q+1) > n ]

---

三、图论经典结论

在任意 n 个点的无向图（或补图）中，有两个经典定理：

1. Turán 定理的推论：图或其补图中，存在度数至少为 (p) 的点集，且最大团或独立集大小满足一些关系。
   更直接的相关结论是：
   对于任意整数 (p,q \ge 0)，如果 ((p+1)(q+1) > n)，则图中有大小为 (p+1) 的团，或者大小为 (q+1) 的独立集。
   这是 Erdős–Szekeres 型的 Ramsey 理论结论：(R(p+1, q+1) > n) 意味着图或其补图有团或独立集。

   但我们这里条件正好是 ((p+1)(q+1) > n)，那么根据 对称 Ramsey 理论：

   • 要么原图有大小为 (q+1) 的独立集（尴尬聚会取 q 个点就行，注意这里独立集大小是 q+1，我们只需 q 个点，所以更宽松）；
   • 要么补图有大小为 (p+1) 的团，即原图有大小为 (p+1) 的点集，它们之间两两不认识？不对，反了：补图的团对应原图的独立集，补图的独立集对应原图的团。所以还是原图要么有团要么有独立集。

   但我们需要的是：热闹聚会 S 中每个点至少有 p 个邻居在 S 中，这不是要求 S 是团（团中每个点有 |S|-1 个邻居），而是要求最小度数至少 p。所以不是团，是 p-核心（k-core）的概念。

---

四、构造方法

我们需要找到两个点集 (S_1)（热闹）、(S_2)（尴尬），它们的参数 p 和 q 满足 ((p+1)(q+1) > n)。

关键观察：

• 热闹聚会的 p 就是 S1 中点的最小度数（在诱导子图中）。
• 尴尬聚会的 q 就是 S2 的大小（且 S2 是独立集）。

我们可以固定 q，然后找一个 p 尽可能大的 S1。
根据条件 ((p+1)(q+1) > n)，有 (p > n/(q+1) - 1)。
所以只要找到一个子图，其最小度数 (d_{\min} \ge \lfloor n/(q+1) \rfloor)，即可取 (p = d_{\min})，条件自动满足（因为 (\lfloor n/(q+1) \rfloor \le p) 就是条件之一，而另一条件 (\lfloor n/(p+1) \rfloor \le q) 也会由 ((p+1)(q+1) > n) 保证）。

---

更简单的做法是：

1. 找尴尬聚会 S2：
   在图中找一个较大的独立集（可以用贪心：按度数从小到大依次取点，不与已取的点相邻就加入）。设找到的独立集大小为 (q)。

2. 找热闹聚会 S1：
   在图中找一个 k-core（反复删除度数小于 k 的点，直到不能删为止），其中 k 尽量大。取 k-core 作为 S1，其最小度数 (p \ge k)。
   我们要让 p 和 q 满足 ((p+1)(q+1) > n)。

3. 调整：
   如果独立集 q 太小，就稍微降低 k，让 k-core 更大，从而 q 可能增大吗？不对，q 是独立集，与 S1 无关。
   其实我们可以用已知结论：对于任意图，存在一个子图（k-core）的最小度数至少为某个值，并且该值和最大独立集大小满足那个不等式。
   标准构造方法：

   • 对 (d = 0) 到 (n-1)，考虑 d-core（如果存在）。设其大小为 s，最小度数为 (p \ge d)。
   • 在补图中找独立集（即在原图中找团……不对，尴尬聚会在原图中是独立集，与原图有关）。
   • 其实可以直接从 1 到 n 枚举 p，看能否找到 p-core 且满足 ((p+1)(q+1) > n)，其中 q 是最大独立集大小下界。
     最大独立集大小至少为 (n/(\Delta+1)) 之类的界，但这里我们需要一个构造。

---

实际上，标准解法是：

1. 找原图的极大独立集 I（比如贪心），令 (q = |I|)。
2. 我们知道图中有独立集大小为 q，那么根据 Turán 定理的推广，图中有度至少为 (p = \lfloor n/(q+1) \rfloor) 的点（甚至子图）。
   如何找？
   可以用剥皮（peeling）方法：反复删除图中最小度数的点，记录删除时的度数。
   有一个性质：当删除到剩余 r 个点时，这些点最小度数 ( \ge \lfloor n/(q+1) \rfloor )，其中 q 是独立集大小。
   更精确的：若最大独立集大小为 (\alpha(G))，那么存在一个子图最小度数至少为 (\lfloor n/\alpha(G) \rfloor - 1)。
   所以取 (p = \lfloor n/q \rfloor - 1)（q 是独立集大小，不是最大独立集，但 q 是某个独立集大小），那么 ((p+1)(q+1) \ge (\lfloor n/q \rfloor)(q+1) > n) 可能成立。

---

五、构造步骤（可直接实现）

由于题目不要求 p, q 最大，只要求存在，我们可以这样：

1. 求尴尬聚会：
   用贪心法求一个极大独立集 I（按度数从小到大排序，依次取不与已取点相邻的点）。令 (q = |I|)。

2. 求热闹聚会：
   对 (k = \lfloor n/(q+1) \rfloor)，在图中找 k-core（反复删除度数小于 k 的点）。设得到的子图为 H。
   如果 H 非空，那么 H 的最小度数至少为 k，取 (p = k)。
   条件 ((p+1)(q+1) > n) 显然成立，因为 (p = \lfloor n/(q+1) \rfloor)，所以 ((p+1) > n/(q+1))，即 ((p+1)(q+1) > n)。

   如果 H 为空，则降低 k 直到 H 非空（比如 k=0 肯定非空，但我们要满足不等式）。
   但若 H 为空，说明所有点度数小于 k，那么独立集可以更大吗？我们可能需重新调整：如果 k 太大导致 H 为空，就减小 k 直到 H 非空，同时可能 q 会变化（但 q 已经固定为独立集大小）。
   我们其实只需保证最终得到的 (p)（H的最小度数）和 (q) 满足不等式，而一旦 (p = \lfloor n/(q+1) \rfloor) 时 H 非空，不等式就成立。

3. 验证：
   若 H 非空，热闹聚会取 H 的所有点，尴尬聚会取独立集 I 的点。
   它们满足： [ \left\lfloor \frac{n}{p+1} \right\rfloor = \left\lfloor \frac{n}{\lfloor n/(q+1) \rfloor + 1} \right\rfloor \le q ] 另一个 (\lfloor n/(q+1) \rfloor \le p) 也成立。

---

六、样例分析

样例1： n=6, m=15（完全图）。
独立集大小 q=1（任意两点都认识，只能取一个点）。
计算 k = floor(6/(1+1)) = 3。
找 3-core：完全图的 3-core 就是整个图（最小度数 5≥3），所以 H 有 6 个点，最小度数 p=5。
输出热闹聚会 6 个点，尴尬聚会 1 个点（比如 4）。

样例2： n=8, m=11（给定图）。
贪心独立集：比如 {8,4,7,2} 大小 q=4。
k = floor(8/5)=1。
找 1-core：删除孤立点？没有孤立点，1-core 就是整个图，最小度数至少 1，所以 p≥1。
热闹聚会可以取所有 8 个点，尴尬聚会取那 4 个点。

---

七、正确性证明概要

1. 独立集 I 的大小 q 是可行的尴尬聚会。
2. 取 (k = \lfloor n/(q+1) \rfloor)，如果 k-core 非空，则其最小度数 (p \ge k)。
   那么 (\lfloor n/(q+1) \rfloor = k \le p)，且 ((p+1)(q+1) > n) 成立（因为 (p+1 > n/(q+1))），从而 (\lfloor n/(p+1) \rfloor \le q)。
3. 如果 k-core 为空，则所有点度数小于 k，那么独立集大小可以更大，矛盾于贪心独立集的最大性？不一定，但我们可以减小 k 直到 k-core 非空（比如 k=1 一定非空），仍满足不等式，因为减小 k 会减小 p，但条件对更小的 p 也可能成立（需要验证，不过题解标准做法是直接取 k 为某个值保证非空）。

实际比赛中，由于时间限制，我们只需找到一个可行解，不需最优。可以枚举 p，对每个 p 找 p-core，然后找补图的独立集（原图的团？不对，尴尬聚会是原图的独立集），两个集合无关，只要参数满足不等式就行。

---

八、实现注意事项

• 由于 n 最大 10000，m 最大 1e5，可以用邻接表存图。
• 求 k-core 是 O(n+m) 的（用队列反复删点）。
• 求极大独立集贪心 O(n log n + m)。
• 多组数据总复杂度可接受。
• 注意读入优化，数据量较大。

---

总结

这道题的关键是将抽象的不等式转化为 ((p+1)(q+1) > n)，然后利用图的性质：

• 尴尬聚会对应独立集
• 热闹聚会对应 k-core（最小度数至少 k 的子图）

构造时先找独立集确定 q，再取合适的 k 找 k-core 得到 p，自动满足不等式。
这是一种存在性构造，不要求极值，所以实现相对直接。