#include<algorithm>
#include<vector>
#include<ctime>
#include<cstring>
#include<cctype>
#include<cstdio>
using namespace std;
inline int readint(){
int x=0;
bool f=0;
char c=getchar();
while(!isdigit(c)&&c!='-') c=getchar();
if(c=='-'){
f=1;
c=getchar();
}
while(isdigit(c)){
x=x*10+c-'0';
c=getchar();
}
return f?-x:x;
}
const int maxn=1e4+5;
int n,m;
vector<int> g[maxn];
int deg[maxn];
bool vis[maxn];
void dfs(int u,int p){
vis[u]=1;
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if(vis[v]) continue;
deg[v]--;
if(deg[v]<p) dfs(v,p);
}
}
void check(int p){
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++) deg[i]=g[i].size();
for(int i=1;i<=n;i++)
if(!vis[i]&&deg[i]<p) dfs(i,p);
}
int ord[maxn];
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
srand(time(0)*20060122);
int t=readint();
while(t--){
n=readint();
m=readint();
for(int i=1;i<=n;i++) g[i].clear();
for(int i=0;i<m;i++){
int u,v;
u=readint();
v=readint();
g[u].push_back(v);
g[v].push_back(u);
}
int l=0,r=n-1;
while(l<r){
int mid=l+(r-l+1)/2;
check(mid);
bool ok=0;
for(int i=1;i<=n;i++) if(!vis[i]){
ok=1;
break;
}
if(ok) l=mid;
else r=mid-1;
}
check(r);
int cnt=0;
for(int i=1;i<=n;i++) if(!vis[i]) cnt++;
printf("%d ",cnt);
for(int i=1;i<=n;i++) if(!vis[i]) printf("%d ",i);
printf("\n");
for(int i=1;i<=n;i++) ord[i]=i;
random_shuffle(ord+1,ord+n+1);
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++){
int ok=1;
for(int j=0;j<g[ord[i]].size();j++)
if(vis[g[ord[i]][j]]){
ok=0;
break;
}
if(ok) vis[ord[i]]=1;
}
cnt=0;
for(int i=1;i<=n;i++) if(vis[i]) cnt++;
printf("%d ",cnt);
for(int i=1;i<=n;i++) if(vis[i]) printf("%d ",i);
printf("\n");
}
return 0;
}

#include<algorithm>
#include<vector>
#include<ctime>
#include<cstring>
#include<cctype>
#include<cstdio>
using namespace std;
inline int readint(){
int x=0;
bool f=0;
char c=getchar();
while(!isdigit(c)&&c!='-') c=getchar();
if(c=='-'){
f=1;
c=getchar();
}
while(isdigit(c)){
x=x*10+c-'0';
c=getchar();
}
return f?-x:x;
}
const int maxn=1e4+5;
int n,m;
vector<int> g[maxn];
int deg[maxn];
bool vis[maxn];
void dfs(int u,int p){
vis[u]=1;
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if(vis[v]) continue;
deg[v]--;
if(deg[v]<p) dfs(v,p);
}
}
void check(int p){
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++) deg[i]=g[i].size();
for(int i=1;i<=n;i++)
if(!vis[i]&&deg[i]<p) dfs(i,p);
}
int ord[maxn];
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
srand(time(0)*20060122);
int t=readint();
while(t--){
n=readint();
m=readint();
for(int i=1;i<=n;i++) g[i].clear();
for(int i=0;i<m;i++){
int u,v;
u=readint();
v=readint();
g[u].push_back(v);
g[v].push_back(u);
}
int l=0,r=n-1;
while(l<r){
int mid=l+(r-l+1)/2;
check(mid);
bool ok=0;
for(int i=1;i<=n;i++) if(!vis[i]){
ok=1;
break;
}
if(ok) l=mid;
else r=mid-1;
}
check(r);
int cnt=0;
for(int i=1;i<=n;i++) if(!vis[i]) cnt++;
printf("%d ",cnt);
for(int i=1;i<=n;i++) if(!vis[i]) printf("%d ",i);
printf("\n");
for(int i=1;i<=n;i++) ord[i]=i;
random_shuffle(ord+1,ord+n+1);
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++){
int ok=1;
for(int j=0;j<g[ord[i]].size();j++)
if(vis[g[ord[i]][j]]){
ok=0;
break;
}
if(ok) vis[ord[i]]=1;
}
cnt=0;
for(int i=1;i<=n;i++) if(vis[i]) cnt++;
printf("%d ",cnt);
for(int i=1;i<=n;i++) if(vis[i]) printf("%d ",i);
printf("\n");
}
return 0;
}

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 100010;
#define pi pair<int,int>
ll read() {
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
priority_queue<pi,vector<pi>,greater<pi> >q;
struct node {
int v,nxt;
}e[N << 1];
int head[N],ejs;
void add(int u,int v) {
e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;
}
int vis[N],du[N],tsd[N],bz[N],ans[N],anss[N];
int main() {
// freopen("day2t1.in","r",stdin);
int T = read();
while(T--) {

memset(vis,0,sizeof(vis));
memset(du,0,sizeof(du));
memset(bz,0,sizeof(bz));
ejs = 0;memset(head,0,sizeof(head));

int n = read(),m = read();
for(int i = 1;i <= m;++i) {
int u = read(),v = read();
add(u,v);add(v,u);
du[u]++,du[v]++;
}

for(int i = 1;i <= n;++i) tsd[i] = du[i];

for(int i = 1;i <= n;++i) q.push(make_pair(du[i],i));

int ansjs = 0,js = 0,mx = 0;
while(!q.empty()) {
int d = q.top().first,u = q.top().second;
q.pop();
vis[u] = 1;
if(du[u] != d) continue;
if(d > mx) {
// puts("!!!");
// printf("%d\n",js);
mx = d;
ansjs = js;
}
ans[++js] = u;
for(int i = head[u];i;i = e[i].nxt) {
int v = e[i].v;
if(vis[v]) continue;
du[v]--;q.push(make_pair(du[v],v));
}
}
memset(vis,0,sizeof(vis));
for(int i = 1;i <= n;++i) q.push(make_pair(tsd[i],i));
js = 0;
while(!q.empty()) {
int u = q.top().second,d = q.top().first;
q.pop();
if(vis[u]) continue;
vis[u] = 1;
anss[++js] = u;
if(d != tsd[u]) continue;
// puts("!!!");
for(int i = head[u];i;i = e[i].nxt) {
int v = e[i].v;
// puts("!!!");
if(vis[v]) continue;
vis[v] = 1;
// printf("%d\n",v);
for(int j = head[v];j;j = e[j].nxt) {
int vv = e[j].v;
if(vis[vv]) continue;
--tsd[vv];q.push(make_pair(tsd[vv],vv));
}
}
}
// puts("!!");
for(int i = 1;i <= ansjs;++i) bz[ans[i]] = 1;
printf("%d ",n - ansjs);
for(int i = 1;i <= n;++i) if(!bz[i]) printf("%d ",i);
puts("");
printf("%d ",js);
for(int i = 1;i <= js;++i) printf("%d ",anss[i]);
puts("");

}

return 0;
}

#include<iostream>
#include<cmath>
using namespace std;
int m,n,ans;
int gcd(int x,int y)
{
if(y==0) {return x;}
return gcd(y,x%y);
}
int main()
{
cin>>n>>m;
for(int i=1;i<=sqrt(m*n);i++)
{
if((n*m)%i==0&&gcd(i,(n*m)/i)==n) ans++;
}
cout<<ans*2;
return 0;
}
//SB抄代码