Help johnny to solve this Puzzle
Python, 307 chars

S={'0001001011000':[]}
for i in[0]*7:
 for s in dict(S):
  for m in range(6):S.setdefault(''.join(s[int(x,16)]for x in['2150483769abc','3106428759abc','0326159487abc','0421753986abc','01234587a6c9b','012345976b8ca'][m]),[m]+S[s])
for j in[0]*input():
 L=S[raw_input()];print len(L)
 for m in L:print m/2,m%2


Computes S which is a mapping from a state (a string just like the input) to a list of move numbers which solve the state.  Generates a complete S on startup (only 715 states), then looks up each input and prints the answer.

Moves are implemented using a string of hex digits indicating where each result vertex comes from.

Takes about 0.15 seconds regardless of how big the input is.