两个问题能放在一道题里，说明这两个问题间应该存在点内在联系。

我们先看第一问。

第一问比较简单，我们每次从图上删除度数最小的点，并更新答案，即可确保 $p$ 尽可能大。

而对于求最大独立集，有诸如模拟退火等近似算法。如果有充裕的时间调参，理论上可以得到不错的解。当然这样的做法就和第一问无关了。

针对本题，我们有一种和解第一问差不多的方法：我们仍然每次挑出度数最小的点，把这个点加入独立集，并将与这个点直接相连的点从图中删掉。

可以证明，按照这个方法构造，一定可以满足题目所述限制。

证明如下：

我们每将一个点加入独立集，除去这个点本身外，最多会从图中删掉 $p$ 个点（第一问的结论）。

于是有 $q \geq \left \lceil \dfrac{n}{p+1} \right \rceil$。

#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
struct node
{
 int x,y;
 bool operator<(const node&a)const
 {
  return y>a.y;
 }
};
vector<int> e[10005];
int t[10005],t1[10005],t2[10005],vis[10005];
int ord[10005],res[10005],cnt;
priority_queue<node> q;
int main()
{
 ios::sync_with_stdio(false);
 int T;
 cin>>T;
 while(T--)
 {
  int n,m;
  int ansp=0,ansq=0,pos=0;
  cnt=0;
  cin>>n>>m;
  memset(t,0,sizeof(t));
  for(int i=1;i<=n;i++)
   vector<int>().swap(e[i]);
  for(int i=1;i<=m;i++)
  {
   int u,v;
   cin>>u>>v;
   e[u].push_back(v);
   e[v].push_back(u);
   t[u]++,t[v]++;
  }
  memcpy(t1,t,sizeof(t));
  memcpy(t2,t,sizeof(t));
  memset(vis,0,sizeof(vis));
  for(int i=1;i<=n;i++)
   q.push({i,t[i]});
  ansp=q.top().y;
  while(!q.empty())
  {
   int u=q.top().x;
   q.pop();
   if(vis[u])continue;
   ord[++cnt]=u,vis[u]=1;
   int rp=q.top().y;
   if(rp>ansp)
    ansp=rp,pos=cnt;
   for(auto v:e[u])
   {
    t1[v]--;
    q.push({v,t1[v]});
   }
  }
  memset(vis,0,sizeof(vis));
  for(int i=1;i<=n;i++)
   q.push({i,t[i]});
  while(!q.empty())
  {
   int u=q.top().x;
   q.pop();
   if(vis[u])continue;
   res[++ansq]=u,vis[u]=1;
   for(auto v:e[u])
    vis[v]=1;
  }
  memset(vis,0,sizeof(vis));
  for(int i=1;i<=pos;i++)
   vis[ord[i]]=1;
  cout<<n-pos<<' ';
  for(int i=1;i<=n;i++)
   if(!vis[i])cout<<i<<' ';
  cout<<endl;
  cout<<ansq<<' ';
  for(int i=1;i<=ansq;i++)
   cout<<res[i]<<' ';
  cout<<endl;
 }
 return 0;
}

比较牛的构造题。

首先我们的目标大致是最大化 $p,q$，由于一般图最大独立集不太可做所以我们先来最大化 $p$。

可以尝试二分一个答案 $mid$，不断地将所有度数小于等于 $mid$ 的点以及他们所连的边删去，最后如果图没被删空就代表 $p \geq mid$。

由于构造的 $q$ 的限制与 $p$ 强相关，所以我们考虑在构造最大 $p$ 的过程中顺便构造出满足要求的 $q$，首先我们需要简化最大 $p$ 的构造过程。

考虑从 $\text{check}(x)$ 的过程扩展到 $\text{check(x+1)}$ 的过程，你发现我们只需要再把度数为 $x+1$ 的点也列入删除的范畴即可，于是可以考虑这样一个过程：每次取出度数最小的点删除，并在这个过程中维护一个集合 $S$，如果取出的点度数大于 $S$ 中所有点在被取出时的度数就清空 $S$，否则什么都不做，然后加入这个点本身。那么最后 $S$ 就是构造到最大 $p$ 的一种方案。

然后考虑在这个过程中构造一个合法的 $q$，首先我们可以想到和构造 $p$ 的过程类似的一个贪心求解出一个尽可能大的（显然可能不是最大的）独立集的算法，每次取出度数最小点，如果没有被标记就将其加入独立集并标记其邻域，然后无论其有没有被标记都将其自己与自己所连出的边删去，显然可以在构造 $p$ 的过程中同时进行这个算法，并且注意到每次标记的邻域大小一定不超过 $p$，由于我们的算法会一直进行到图被删空，所以显然至少会有 $\left\lfloor \frac{n}{p+1} \right\rfloor$ 个点被我们加入独立集，故得到了一个合法构造。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4+114;
vector<int> E[maxn];
int d[maxn];
int vis[maxn],del[maxn];
int n,m;
vector<int> S,T;
set< pair<int,int> > q;
void work(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        E[u].push_back(v);
        E[v].push_back(u);
    }   
    for(int i=1;i<=n;i++){
        d[i]=E[i].size();
        q.insert(make_pair(d[i],i));
    }
    int maxd=0;
    while(q.size()>0){
        int u=(*q.begin()).second;
        if(d[u]>maxd) S.clear(),maxd=max(maxd,d[u]);
        S.push_back(u);
        del[u]=1;
        q.erase(make_pair(d[u],u));
        if(vis[u]==0){
            T.push_back(u);
            vis[u]=1;
            for(int v:E[u]) vis[v]=1;
        }
        for(int v:E[u]){
            if(del[v]==1) continue;
            q.erase(make_pair(d[v],v));
            d[v]--;
            q.insert(make_pair(d[v],v));
        }
        E[u].clear();
    }
    cout<<S.size()<<" ";
    for(int x:S) cout<<x<<" ";
    cout<<"\n";
    cout<<T.size()<<" ";
    for(int x:T) cout<<x<<" ";
    cout<<"\n";
    for(int i=1;i<=n;i++) vis[i]=del[i]=0;
    S.clear(),T.clear();
    return ;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--) work();
    return 0;
}