Cod sursa(job #135933)

Utilizator blasterzMircea Dima blasterz Data 14 februarie 2008 21:06:31
Problema Pioni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
using namespace std;

#include <cstdio>
#include <vector>
#include <queue>
#define pb push_back
#define maxn 20001

vector<int> a[maxn];
vector<int>b[maxn];
int gi[maxn],go[maxn];
int SG[maxn];
int n, m, T;
int t[maxn];

void read()
{
  freopen("pioni.in","r",stdin);
  scanf("%d %d %d\n", &T, &n, &m);
  int p, q;
  while(m--)
    {
      scanf("%d %d\n", &p, &q);
      a[p].pb(q);
      b[q].pb(p);
      ++gi[q];
      ++go[p];
    }

}

void bfs()
{
  int i, j, u;
  queue<int>Q;
  vector<int>::iterator it,jt;
  bool use[maxn];
 
  memset(use, 0, sizeof(use));

  memset(SG, -1, sizeof(SG));

  for(i=1;i<=n;++i) if(!go[i]) Q.push(i), use[i]=1, SG[i]=0;
  
  while(!Q.empty())
    {
      u=Q.front();
      Q.pop();

      for(it=b[u].begin();it!=b[u].end();++it)
	if(!use[*it])
	  {
	    i=*it;
	    Q.push(i);
	    bool UZ[150];
	    memset(UZ, 0, sizeof(UZ));

	    for(jt=a[i].begin();jt!=a[i].end();++jt)
	      if(use[*jt])
		UZ[SG[*jt]]=1;

	    for(j=0;j<128;++j)
	      if(!UZ[j]) { SG[i]=j; break;}

	  }
    }
		
	    
      
  

}

int x[30001];
int nd[maxn];


void solve()
{
  int K, i;
  vector<int>::iterator it;

  while(T--)
    {
      scanf("%d ", &K);
      memset(nd, 0, sizeof(nd));
      for(i=1;i<=K;++i) scanf("%d ", &x[i]);
      
      for(i=1;i<=K;++i) ++nd[x[i]];

      int S=1;
      /*
      for(i=1;i<=K;++i)
		  if(SG[x[i]])
		  {
			int oki=0;
			  for(it=a[x[i]].begin();it!=a[x[i]].end();++it)
				if(SG[*it]==0) oki=1;
			if(!oki) S=0;
		  }
    */


      int t=0;

    		int nr=0;
	for(i=1;i<=K;++i) if(!SG[x[i]])++nr;
if(nr) S=0;	
      // printf("%d\n", S);
      if(S==0) printf("Fumeanu\n");
      else
	{
	  printf("Nargy\n");
	  
	  int nr=0;
	  for(i=1;i<=K;++i)
	    {
	      for(it=a[x[i]].begin();it!=a[x[i]].end();++it)
		if(SG[*it]==0) 
		  {
		    ++nr;
		    //printf("%d %d\n", x[i] ,*it);
		    break;
		  }
	    }
	  printf("%d ", nr);
	   for(i=1;i<=K;++i)
	    {
	      for(it=a[x[i]].begin();it!=a[x[i]].end();++it)
		if(SG[*it]==0) 
		  {
		    //++nr;
		    printf("%d %d ", x[i] ,*it);
		    break;
		  }
	      
	    }
	   printf("\n");

	}
    }

}

int main()
{
  read(); 
  int i;
 

  freopen("pioni.out","w",stdout);

  bfs();

  solve();


  return 0;
}