Source Code
Problem: 1333		User: yzhw
Memory: 3120K		Time: 141MS
Language: Java		Result: Accepted

    Source Code

    import java.io.*;
    import java.util.*;
    class node
    {
    	int type,id;
    	BitSet s1,s2;
    }
    public class Main {

    	/**
    	 * @param args
    	 */
    	static StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    	static int nxtInt() throws IOException
    	{
    		in.nextToken();
    		return (int)in.nval;
    	}
    	static BitSet data[]=new BitSet[105];
    	static ArrayList<node> edge=new ArrayList<node>();
    	static int n,m;
    	static boolean include(BitSet a,BitSet b)
    	{
    			BitSet tmp=new BitSet(1000);
    			tmp.clear();
    			tmp.or(a);
    			tmp.or(b);
    			if(tmp.equals(a)) return true;
    			else
    			{
    				a.or(tmp);
    				return false;
    			}
    	}
    	static boolean include(BitSet a,BitSet b,BitSet c,boolean type)
    	{
    			BitSet tmp=new BitSet(1000);
    			tmp.clear();
    			if(!type)
    			{	
    				tmp.or(b);
    				tmp.and(c);
    				tmp.or(a);
    			}
    			else
    			{
    				tmp.or(b);
    				tmp.andNot(c);
    				tmp.or(a);
    			}
    			if(tmp.equals(a)) return true;
    			else
    			{
    				a.or(tmp);
    				return false;
    			}
    			
    	}
    	public static void main(String[] args) throws IOException{
    		  for(int i=0;i<data.length;i++)
    			  data[i]=new BitSet(1000);
    		 
    		  int test=nxtInt();
    		  while((test--)!=0)
    		  {
    			  n=nxtInt();
    			  m=nxtInt();
    			  edge.clear();
    			  for(int i=1;i<=m;i++)
    			  {
    				  int id=nxtInt(),nn=nxtInt();
    				  node tt;
    				  data[id].clear();
    				  while((nn--)!=0)
    					  switch(nxtInt())
    					  {
    					  case -1:
    						  {
    							int num=nxtInt();
    							tt=new node();
    							tt.s1=new BitSet(1000);
    							tt.s1.clear();
    							tt.type=1;
    							tt.id=id;
    							while((num--)!=0)
    								tt.s1.set(nxtInt());
    							edge.add(tt);
    							break;
    						  }	
    					  case -2:
    						  {
    							  tt=new node();
    							  tt.s1=data[nxtInt()];
    							  tt.type=1;
    							  tt.id=id;
    							  edge.add(tt);
    							  break;
    						  }
    					  case -3:
    						  {
    							  tt=new node();
    							  tt.type=3;
    							  tt.id=id;
    							 switch(nxtInt())
    							 {
    							 case -1:
    								 tt.s1=new BitSet(1000);
    								 tt.s1.clear();
    								 for(int num=nxtInt();num>0;num--)
    									 tt.s1.set(nxtInt());
    								 break;
    							 case -2:
    								 tt.s1=data[nxtInt()];
    								 break;
    							 }
    							 switch(nxtInt())
    							 {
    							 case -1:
    								 tt.s2=new BitSet(1000);
    								 tt.s2.clear();
    								 for(int num=nxtInt();num>0;num--)
    									 tt.s2.set(nxtInt());
    								 break;
    							 case -2:
    								 tt.s2=data[nxtInt()];
    								 break;
    							 }
    							 edge.add(tt);
    							 break;
    						  }
    					  case -4:
    						  {
    							  tt=new node();
    							  tt.type=4;
    							  tt.id=id;
    							 switch(nxtInt())
    							 {
    							 case -1:
    								 tt.s1=new BitSet(1000);
    								 tt.s1.clear();
    								 for(int num=nxtInt();num>0;num--)
    									 tt.s1.set(nxtInt());
    								 break;
    							 case -2:
    								 tt.s1=data[nxtInt()];
    								 break;
    							 }
    							 switch(nxtInt())
    							 {
    							 case -1:
    								 tt.s2=new BitSet(1000);
    								 tt.s2.clear();
    								 for(int num=nxtInt();num>0;num--)
    									 tt.s2.set(nxtInt());
    								 break;
    							 case -2:
    								 tt.s2=data[nxtInt()];
    								 break;
    							 }
    							 edge.add(tt);
    							 break;
    						  }
    					  }
    			  }
    			  //start
    			  while(true)
    			  {
    				  boolean flag=false;
    				  for(node tt:edge)
    					  switch(tt.type)
    					  {
    					  case 1:
    						  if(include(data[tt.id],tt.s1)) continue;
    						  else flag=true;
    						  break;
    					  case 3:
    						  if(include(data[tt.id],tt.s1,tt.s2,false)) continue;
    						  else flag=true;
    						  break;
    					  case 4:
    						  if(include(data[tt.id],tt.s1,tt.s2,true)) continue;
    						  else flag=true;
    						  break;
    					  }
    				  if(!flag) break;
    			  }
    			  //print
    			  for(int i=1;i<=m;i++)
    			  {
    				  System.out.print(i);
    				  for(int j=1;j<=n;j++)
    					  if(data[i].get(j))
    						  System.out.print(" "+j);
    				  System.out.println();
    			  }
    		  }
    		  


    	}

    }