What is the Codeforces Round #XXX problem set like?

本文共计1214个文字，预计阅读时间需要5分钟。

A. NP-Hard问题，每测试用例时间限制2秒，每测试用例内存限制256MB。输入标准输入，输出标准输出。最近，Pari和Arya对NP-Hard问题进行了研究，他们发现了最小顶点覆盖问题。

A. NP-Hard Problem

time limit per test 2 seconds

memory limit per test 256 megabytes

input standard input

output standard output

Recently, Pari and Arya did some research about NP-Hard problems and they found theminimum vertex cover

Suppose the graphGis given. SubsetAof its vertices is called avertex coverof this graph, if for each edgeuvthere is at least one endpoint of it in this set, i.e.

or

(or both).

Pari and Arya have won a great undirected graph as an award in a team contest. Now they have to split it in two parts, but both of them want their parts of the graph to be a vertex cover.

They have agreed to give you their graph and you need to find twodisjointsubsets of its verticesAandB, such that bothAandB

Input

The first line of the input contains two integersnandm(2 ≤ n ≤ 100 000,1 ≤ m ≤ 100 000)— the number of vertices and the number of edges in the prize graph, respectively.

Each of the nextmlines contains a pair of integersuiandvi(1  ≤  ui,  vi  ≤  n), denoting an undirected edge betweenuiandvi. It's guaranteed the graph won't contain any self-loops or multiple edges.

Output

If it's impossible to split the graph between Pari and Arya as they expect, print "-1" (without quotes).

If there are two disjoint sets of vertices, such that both sets are vertex cover, print their descriptions. Each description must contain two lines. The first line contains a single integerkdenoting the number of vertices in that vertex cover, and the second line containskintegers— the indices of vertices. Note that because ofm ≥ 1, vertex cover cannot be empty.

Examples

input

4 2
1 2
2 3

output

1
2
2
1 3

input

3 3
1 2
2 3
1 3

output

-1

Note

In the first sample, you can give the vertex number2to Arya and vertices numbered1and3to Pari and keep vertex number4

In the second sample, there is no way to satisfy both Pari and Arya.

题解：多校结束了，写道题压压惊。。。给你一些顶点和边，将顶点分为两组，同一组的任意两个顶点不能相连。输出两组的各点，若不能分，输出-1。

代码：

#pragma comment(linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
#include<cmath>
#include<queue>
#include<set>
#include<stack>
#include <utility>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define mst(a) memset(a, 0, sizeof(a))
#define M_P(x,y) make_pair(x,y)
#define pii pair<int,int>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
#define lson x << 1, l, mid
#define rson x << 1 | 1, mid + 1, r
const int lowbit(int x) { return x&-x; }
const double eps = 1e-8;
const int INF = 1e9+7;
const ll inf =(1LL<<62) ;
const int MOD = 1e9 + 7;
const ll mod = (1LL<<32);
const int N = 2e5+10;
const int M=100010;
template <class T1, class T2>inline void getmax(T1 &a, T2 b) {if (b>a)a = b;}
template <class T1, class T2>inline void getmin(T1 &a, T2 b) {if (b<a)a = b;}
int read()
{
int v = 0, f = 1;
char c =getchar();
while( c < 48 || 57 < c ){
if(c=='-') f = -1;
c = getchar();
}
while(48 <= c && c <= 57)
v = v*10+c-48, c = getchar();
return v*f;
}
vector<int>G[100010];
vector<int>ans[2];
int vis[100010];
int ok;
int type[100010];
void dfs(int u,int fa,int ty) //u的父亲是fa
{
ans[ty].push_back(u); //存储二分图
vis[u]=1;
type[u]=ty;
int d=G[u].size(); //结点u的相邻点个数
for(int i = 0;i< d ;i++)
{
int v = G[u][i]; //结点u的第i个相邻点v
if(v==fa)
continue;
if(vis[v]&&type[v]==type[u])
ok=1;
if(vis[v])
continue;
dfs(v,u,1-ty); //把 v 的父亲设为 u，继续递归
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int n,m;
ok = 0;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
for(int i = 1;i <= n; i++)
if(!vis[i]&&!ok)
dfs(i,-1,0);
if(ok)
{
puts("-1");
return 0;
}
printf("%d\n",ans[0].size());
for(int i=0;i<ans[0].size()-1;i++)
printf("%d ",ans[0][i]);
printf("%d\n",ans[0][ans[0].size()-1]);

printf("%d\n",ans[1].size());
for(int i=0;i<ans[1].size()-1; i++)
printf("%d ",ans[1][i]);
printf("%d\n",ans[1][ans[1].size()-1]);
return 0;
}