Codeforces NP-Hard Problem Solution

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.List;

import java.util.StringTokenizer;

public class Div360 {

static int color[];

static LinkedList<Integer> q;

public static void main(String[] args) {

// TODO Auto-generated method stub

MyScannerdiv360 sc=new MyScannerdiv360();

int n=sc.nextInt();

int m=sc.nextInt();

q=new LinkedList<Integer>();

List<Integer> g[]=new ArrayList[n];

int i;

color=new int[n];

for(i=0;i<n;i++)

{

g[i]=new ArrayList<Integer>();

}

for(i=0;i<m;i++)

{

int u=sc.nextInt();

int v=sc.nextInt();

g[u-1].add(v-1);

g[v-1].add(u-1);

}

boolean flag=false;

List<Integer> a=new ArrayList<Integer>();

List<Integer> b=new ArrayList<Integer>();

for(i=0;i<n;i++)

{

if(color[i]==0)

{

flag=isbipartite(i,g);

if(!flag)

{

System.out.println(-1);

return;

}

}

if(color[i]==1)

a.add(i+1);

else

b.add(i+1);

}

System.out.println(a.size());

for(Integer v:a)

System.out.print(v+" ");

System.out.println();

System.out.println(b.size());

for(Integer v:b)

System.out.print(v+" ");

}

public static boolean isbipartite(int root,List<Integer> g[])

{

color[root]=1;

q.add(root);

while(!q.isEmpty())

{

Integer n=q.poll();

for(Integer v: g[n])

{

if(color[v]==0)

{

if(color[n]==1)

color[v]=2;

else

color[v]=1;

q.add(v);

}

else if(color[v]==color[n])

{

return false;

}

}

}

return true;

}

}

class MyScannerdiv360

{

BufferedReader br;

StringTokenizer st;

MyScannerdiv360()

{

br=new BufferedReader(new InputStreamReader(System.in));

}

String next()

{

while(st==null || !st.hasMoreTokens())

{

try

{

st=new StringTokenizer(br.readLine());

}

catch(Exception e)

{

e.printStackTrace();

}

}

return st.nextToken();

}

int nextInt()

{

return Integer.parseInt(next());

}

long nextLong()

{

return Long.parseLong(next());

}

double nextDouble()

{

return Double.parseDouble(next());

}

String nextLine()

{

String str="";

try

{

str=br.readLine();

}

catch(Exception e)

{

e.printStackTrace();

}

return str;

}

}