[Home|Training|Problems|Contests|C Language] [Login|Register]
 Problems Status Rank Problem 1060 Brand New Game Time Limit: 1000msMemory Limit: 65536kb Description Alice and Bob are fond of a new interesting game. In this game, they play by turns in a Directed Acyclic Graph (DAG). Every node of the graph is assigned a non-negative integer at the beginning. Each round a player must choose a node having a positive integer and transfer 1 to every of its succeeding nodes.Its integer decreases by 1 and all its succeeding node’s integer increases by 1. If the node doesn't have any succeeding nodes, only decrease the node's integer. Who can not find such a node to transfer will lose. The integer whose number is 0 has at least 1 succeeding node. Before playing the game, they come to an agreement about the integer assignment. Alice plays first. To be fair, Bob is responsible for assigning an integer to each node. But there is a constraint: the sum of all integers must be a predetermined value that they both agree. Now, given the sum, Alice wonders how many distinct assignments which will prevent her from winning. Two assignments are different if there is one node assigned different integers in the two assignments. Alice and Bob are so smart that they can always find the best strategy. Input The first line is a number indicating the number of test cases. The first line of each test case includes three number N, M and S (2<=N<=100, 1<=M<=10000, 1<= S <=10000) indicating the number of nodes, the number of edges and the sum of all integers respectively. Nodes are numbered by 0…N-1. The following M lines each have two integers, u and v, indicating an edge from u to v (0 <= u, v
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 0.9ms with 1 query(s).