Sphere Online Judge

Because of maintenance, it is currently impossible to submit any solutions. The maintenance will end around 3:00 am GMT (4:00 am SPOJ time).

This message will disappear once the maintenance is finished.

SPOJ Problem Set (classical)

10930. Dixon Dominoes

Problem code: DIXDOOM


Dixon was in his house, he was a little bored, so he took some dominoes from the case and started thinking: “It is possible to use Qx pieces from the Dominoes so it can make a simulation of a game?” so, Dixon is not a super programmer, but he knows a little bit of constraints in the problems, so he will give it to you, your task, if you choose to accept it, is to find all the possible ways of some N pieces of Domino can be joined together to make a game simulation using exactly Qx dominoes pieces. If you can’t do this, you should print “0”



The input will consists of an integer T, denoting the number of test cases, next, T cases will follow, every case starts with 2 lines N and Q, being N the number of dominoes David has and Q the number of queries you should do, then, N lines will follow, denoting the two parts of a domino piece, as you may know, the domino piece is split in two, so you can join by any side another piece, after this, Q lines will follow, denoting the number of piece you must use to build the game simulation.










You should output all the possible ways to form a game using Qx pieces (with any possible permutation too), as this number can grow very huge, we need you to print the output modulo 31337.


Sample Input:

4 3
2 3
3 1
1 4
4 3
2 1
1 2
1 2
2 1
1 1
1 1


Sample Output:








Domino idea credits goes to: Daniel Ampuero and Luis Arguello


Example of the output with the first case and Q=4

solution 1: joining the pieces 1,2,3 and 4

solution 2: joining the pieces 4,3,2 and 1

solution 3: joining the pieces 2,3,4 and 1

solution 4: joining the pieces 1,4,3 and 2


Tip: In the case with one piece only, you can form a game starting with the two faces of every single piece, i.e. if we want to form a game using just the piece "2 1", one possible game is "2 1" and the other "1 2", resulting in two different ways.

Added by:David Moran
Time limit:6s
Source limit:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Resource:Own Problem

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.