Problem: grundy_graph (2016 finals)

Alice and Bob are spending the day in the local library, learning about
2-player zero-sum games. One of the books they're reading, "Grundy Numbers For
Fun And Profit" by Nim Nimberly, has an interactive insert with a bunch of
graphs and instructions for a game where the players take turns colouring each
graph's vertices.

Each game starts with a directed graph that has 2***N** vertices, numbered
from 1 to 2***N**, all of which are initially uncoloured, and **M** edges. The
**i**th edge goes from vertex **Ai** to vertex **Bi**. No two edges connect
the same pair of vertices in the same direction, and no edge connects a vertex
to itself.

Alice goes first and colours vertices 1 and 2. She must colour one of these
two vertices black, and the other one white. Bob then takes his turn and
similarly colours vertices 3 and 4, one of them black and the other one white.
This continues with Alice colouring vertices 5 and 6, Bob colouring 7 and 8,
and so on until every vertex is coloured. At the end of the game, Alice wins
if there are no edges going from a black vertex to a white one. Bob wins if
such an edge exists.

Who will win if Alice and Bob play optimally?

### Input

Input begins with an integer **T**, the number of graphs. For each graph,
there is first a line containing the space-separated integers **N** and **M**.
Then **M** lines follow, the **i**th of which contains the space-separated
integers **Ai** and **Bi** .

### Output

For the **i**th graph, print a line containing "Case #**i**: " followed by the
winner of the game, either "Alice" or "Bob".

### Constraints

1 ≤ **T** ≤ 45  
1 ≤ **N** ≤ 500,000  
0 ≤ **M** ≤ 500,000  
1 ≤ **Ai**, **Bi**, ≤ 2***N**  

### Explanation of Sample

For the first graph, Alice can color vertex 1 white and vertex 2 black. Since
all edges start at vertex 1, Alice will win. For the second graph, Alice can't
control the color of vertex 3. If Bob makes it white, then one of the two
edges must be from a black vertex to a white vertex, so Bob wins.



Sample input:
5
2 3
1 2
1 3
1 4
2 2
1 3
2 3
5 4
3 6
4 5
8 9
9 10
500000 0
10 10
10 2
6 3
6 19
7 10
14 2
1 11
6 11
1 14
6 14
4 14


Sample output:
Case #1: Alice
Case #2: Bob
Case #3: Bob
Case #4: Alice
Case #5: Alice



Code: // GRUNDY GRAPH
// Official Solution by Jacob Plachta

#define DEBUG 0

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }
string plural(string s) { return(Sz(s) && s[Sz(s)-1]=='x' ? s+"en" : s+"s"); }

const int INF = (int)1e9;
const LD EPS = 1e-9;
const LD PI = acos(-1.0);

//#if DEBUG
#define GETCHAR getchar
/*#else
#define GETCHAR getchar_unlocked
#endif*/

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=GETCHAR();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

#define LIM 2000002

struct edge{int e, nxt;};
int V, E;
edge e[LIM], er[LIM];
int sp[LIM], spr[LIM];
int group_cnt, comp[LIM];
bool v[LIM];
int stk[LIM];
void fill_forward(int x)
{
  int i;
  v[x]=true;
  for(i=sp[x];i;i=e[i].nxt) if(!v[e[i].e]) fill_forward(e[i].e);
  stk[++stk[0]]=x;
}
void fill_backward(int x)
{
  int i;
  v[x]=false;
  comp[x]=group_cnt;
  for(i=spr[x];i;i=er[i].nxt) if(v[er[i].e]) fill_backward(er[i].e);
}
void add_edge(int v1, int v2) //add edge v1->v2
{
  e [++E].e=v2; e [E].nxt=sp [v1]; sp [v1]=E;
  er[  E].e=v1; er[E].nxt=spr[v2]; spr[v2]=E;
}
void SCC()
{
  int i;
  stk[0]=0;
  memset(v, false, sizeof(v));
  for(i=1;i<=V;i++) if(!v[i]) fill_forward(i);
  group_cnt=0;
  for(i=stk[0];i>=1;i--) if(v[stk[i]]){group_cnt++; fill_backward(stk[i]);}
}

int val[LIM];
bool visA[LIM],visB[LIM];
vector<int> con[LIM];

bool rec(int s,int i)
{
		if ((i!=s) && ((i-1)/2%2))
			return(1);
		if (visB[i])
			return(0);
	visB[i]=1;
	int j;
		Fox(j,Sz(con[i]))
			if (rec(s,con[i][j]))
				return(1);
	return(0);
}

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	int T,t;
	int N,M;
	int i,j,a,b;
	Read(T);
		Fox1(t,T)
		{
			printf("Case #%d: ",t);
			Read(N),Read(M);
			N<<=1;
				Fox1(i,N)
					con[i].clear();
			V=N;
			E=0;
			Fill(sp,0);
			Fill(spr,0);
				while (M--)
				{
					Read(i),Read(j);
					con[i].pb(j);
					add_edge(i,j);
						if (j%2)
							j++;
						else
							j--;
						if (i%2)
							i++;
						else
							i--;
					con[j].pb(i);
					add_edge(j,i);
				}
			SCC();
			Fill(visA,0);
			Fill(visB,0);
				Fox1(i,N)
				{
					//Alice
					a=comp[i],b=comp[i+1];
						if (a==b)
							goto Bad;
					visA[a]=visA[b]=1;
					i+=2;
					//Bob
					a=comp[i],b=comp[i+1];
						if ((visA[a]) || (visA[b]) || (rec(i,i)) || (rec(i+1,i+1)))
							goto Bad;
					i++;
				}
			printf("Alice\n");
			continue;
Bad:;
			printf("Bob\n");
		}
	return(0);
}