CF1033E Hidden Bipartite Graph

题目中只能询问一个集合内部的边，我们先考虑如何询问一个点到其他点的边，显然可以把这个询问拆成两个询问，然后我们发现可以在$\log_2$的时间内寻找一个点的任意一条出边（二分）。所以我们考虑先整出一个dfs树。复杂度为$2*n\log_2n$。

这样我们就得到了二分图的“两半”。只需要询问一下两半内部有没有边就能确定是否是二分图。如果是就直接输出。不是的话则遍历内部有边的那一半节点，然后依次询问每个点出发到自己所在的一半有没有边，有边的话暴力找出即可。复杂度$2*n+n$。

计算得出最坏需要13800次询问，符合要求。

/*
                                                  
  _|_|                              _|  _|    _|  
_|    _|  _|  _|_|  _|_|_|_|        _|  _|  _|    
_|    _|  _|_|          _|          _|  _|_|      
_|    _|  _|          _|      _|    _|  _|  _|    
  _|_|    _|        _|_|_|_|    _|_|    _|    _|  
                                                                                                    
*/ 
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
//#define ls (rt<<1)
//#define rs (rt<<1|1)
#define vi vector<int>
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define fi first
#define se second
typedef long long ll;
using namespace std;
const int maxn=605;
int nask(vi tmp){
	if(!tmp.size()||tmp.size()==1)return 0;
	cout<<"? "<<tmp.size()<<endl;
	rep(i,0,(int)tmp.size()-1)cout<<tmp[i]<<' ';
	cout<<endl;
	cout.flush();
	int ans;cin>>ans;
	if(ans==-1)exit(0);
	return ans;
}
int dask(int u,vi tar){
	int cntsig=nask(tar);tar.pb(u);
	int cnttot=nask(tar);
	return cnttot-cntsig;
}
int n;
bool vis[maxn];
int bl[maxn];
int find(int u,vi tmp){
	vi c1,c2;
	if(tmp.size()==1)return tmp[0];
	rep(i,0,(int)(tmp.size())-1){
		if(c1.size()<tmp.size()/2)c1.pb(tmp[i]);
		else c2.pb(tmp[i]);
	}
	if(dask(u,c1))return find(u,c1);
	else return find(u,c2);
}
vi half[2];
vi side[maxn];
void dfs(int u){
	half[bl[u]].pb(u);
	while(1){
		vi tmp;rep(i,1,n)if(!vis[i])tmp.pb(i);
		if(dask(u,tmp)==0)return;
		int tar=find(u,tmp);side[u].pb(tar);side[tar].pb(u);
	//	cout<<">>>"<<u<<"---->"<<tar<<endl;
		vis[tar]=1;bl[tar]=bl[u]^1;dfs(tar);
	}
}
int stk[maxn],top;
vi ans;
void cfs(int u,int tar){
	stk[++top]=u;
	if(u==tar){
		rep(i,1,top)ans.pb(stk[i]);
		return;
	}
	rep(i,0,side[u].size()-1){
		int v=side[u][i];
		if(!vis[v]){
			vis[v]=1;
			cfs(v,tar);
		}
	}
	top--;
}
void ans_out(int u,int v){
	memset(vis,0,sizeof(vis));
	vis[u]=1;cfs(u,v);
	cout<<"N "<<ans.size()<<endl;
	rep(i,0,(int)(ans.size())-1)cout<<ans[i]<<' ';
	return;
}
int main(){
//	freopen("in","r",stdin);
	ios::sync_with_stdio(0);
	cin>>n;
	vis[1]=1;dfs(1);
	if(!nask(half[0])&&!nask(half[1])){
		cout<<"Y "<<half[0].size()<<endl;
		rep(i,0,(int)(half[0].size())-1)cout<<half[0][i]<<' ';
		return 0;
	}
	else{
		rep(i,0,1)rep(j,0,(int)(half[i].size())-1){
			vi tmp;int u=half[i][j];
			rep(k,0,(int)(half[i].size())-1)if(half[i][k]!=u)tmp.pb(half[i][k]);
			if(dask(u,tmp)){
				rep(k,0,(int)(tmp.size())-1){
					vi gg;gg.pb(u);gg.pb(tmp[k]);
					if(nask(gg)){
						ans_out(u,tmp[k]);return 0;
					}
				}
			}
		}
	}
}