DTRAP  Dexters Trampoline
Dexter studies in Huber Elementary School, so does his arch rival Mandark. The school planned a fun trip to a carnival for N students. Everyone’s happy. Mandark has devised a plan to ruin the trip. He knows that there exist many groups within the students. Students of one group are friends with each other but not with any student of other groups. His plan is to instigate a fight among them.
At the carnival, all students line up for time on a trampoline. Dexter learns about Mandark’s plan and knows that If two students that are not friends get on the trampoline at the same time, a fight will start. Suddenly his ‘lab alert’ buzzes. Deedee is trying to break into the lab again! Dexter has to get back home to defend his lab as soon as possible, but he can’t let Mandark ruin the trip.
The trampoline can handle a total weight of W kgs. The students are getting impatient to get on the trampoline. To save time and to avoid a fight, Dexter decides that he will select the first batch of students to go on the trampoline in such a way that their total weight exactly equals W and that no two students are not friends. Your job is to tell him the number of ways he can do this. Dexter has the knowledge of only M pairs of friends.
INPUT:
The first line contains T, the number test cases. T test cases follow. The first line of each test case contains three integers N, W and M. The next line contains N integers, The ith integer is the weight of the ith student (1<=i<=N). The next M lines contain two integers, q and w; this tells that student q and student w are friends.
OUTPUT:
For each test case, output a line containing a single integer, the number of ways Dexter can choose the first batch of students to get on the trampoline.
CONSTRAINTS:
1<=T<=10
1<=N<=22
1<=q,w<=N
0<=M<=(N*(N+1))/2
1<=W<=1500
1<=Weight of each student<=60
Assume that the max number of students on the trampoline has no limit. Only the max weight on the trampoline has the limit W.
SAMPLE TEST CASES:
INPUT:
2
10 90 5
20 30 10 20 30 50 40 20 40 50
1 2
2 3
3 4
4 5
9 10
5 57 3
20 10 96 20 1
1 2
2 3
1 3
OUTPUT:
3
0
EXPLANATION:
For first test case, the following three ways are possible. Using student number,
(1,2,3,5)
(2,3,4,5)
(9,10)
For the second test case, no way is possible for total weight of selected students to be exactly W.
hide comments
ebraheemahmed:
20180816 15:49:05
Does bitmasking work with this problem ?? 

sandip_coder:
20170328 15:58:13
Accepted.... Last edit: 20170328 15:58:59 

:D:
20150329 21:07:06
Note that you shouldn't assume more about friend relation that you can from input information. In particular, for M = 0, you should assume that every student is NOT a friend of every other student. As Abhinav suggested that doesn't mean the result will always be 0. 

Abhinav92003:
20140201 07:58:33
@Anubhav Not necessarily 

Anubhav Balodhi :
20140111 20:59:58
what if Dexter has no knowledge of pair of friends , M=0 ?! The output should be 0 ?! 

Anubhav Balodhi :
20140111 20:59:57
what if Dexter has no knowledge of pair of friends , M=0 ?! The output should be 0 ?! 

Arun Banala:
20131025 11:54:13
Last edit: 20131027 13:26:00 
Added by:  Abhinav92003 
Date:  20131005 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 