Under construction

Still being built. Things may change

Bot or not

Interview

Time limit2sMemory limit512 MB

Summary
Score pairs of secondary accounts by shared posts they follow, then count accounts similar to a known human.
Level

Medium6 of 10

Topics
Implementation, Hash map, Brute force
Solved
No attempts yet

Problem

Fake news spreads mostly through bot accounts. A bot follows other accounts and reposts their stories so that it looks like a person. Bots and people repost in different patterns. Use that difference to decide which accounts are human.

There are two kinds of accounts: pp primary accounts that post stories, and ss secondary accounts that repost stories from primary accounts. For each secondary account you get the primary accounts it follows, whether it is known to be human, and the list of posts it reposted. Assume a secondary account sees every post made by every primary account it follows. Leaving a post it saw without a repost is therefore a deliberate choice.

The similarity score of two secondary accounts is set by three integers w0w_0, w1w_1, w2w_2 with w1<0<w0,w2w_1 < 0 < w_0, w_2. Only the posts of primary accounts that both secondary accounts follow enter the score. For each such post, if jj of the two accounts reposted it, add wjw_j. Both reposting or neither reposting gives a positive score, and a repost by exactly one of them gives the negative score w1w_1. If the two accounts follow no primary account in common, their score is 0.

Two accounts are similar if their total score is at least the threshold tt. A secondary account is judged human if it is similar to an account known to be human. Being similar to an account that was judged human does not make an account human, so the judgement applies only one step.

For each data set, count the secondary accounts that are known human or judged human.

Input

The first line contains the number of data sets KK. The KK data sets follow, each in this format.

The first line of a data set contains six integers pp, ss, w0w_0, w1w_1, w2w_2, tt. Here 1≤p≤1001 \le p \le 100 is the number of primary accounts, 1≤s≤1001 \le s \le 100 is the number of secondary accounts, −100≤w1<0<w0,w2≤100-100 \le w_1 < 0 < w_0, w_2 \le 100 are the similarity scores, and 0≤t<1000000 \le t < 100000 is the similarity threshold.

The next line contains pp integers mim_i (0≤mi≤10000 \le m_i \le 1000), where mim_i is the number of posts made by primary account ii. Posts are numbered from 1: the first m1m_1 posts belong to primary account 1, the next m2m_2 posts to primary account 2, and so on.

The next ss lines describe one secondary account jj each. A line starts with the integer hjh_j, which is 1 if the account is known to be human and 0 if it is not known whether it is human or a bot. Next comes the integer fjf_j (0≤fj≤p0 \le f_j \le p), the number of primary accounts that jj follows, followed by fjf_j distinct integers between 11 and pp, the indices of those primary accounts. Next comes the integer rjr_j (0≤rj≤∑imi0 \le r_j \le \sum_i m_i), the number of reposts made by jj, followed by rjr_j distinct integers between 11 and ∑imi\sum_i m_i, the posts that jj reposted. No input has an account reposting a post of a primary account it does not follow.

Output

For each data set, print Data Set x: on a line of its own, where xx is the number of the data set counting from 1. On the next line print the number of secondary accounts that are known human or judged human. Print one blank line after each data set.

Examples5

  1. Example 1

    Input
    1
    3 3 1 -4 5 8
    5 3 6
    0 1 2 3 8 7 6
    1 2 1 3 6 1 9 10 13 14 5
    0 2 2 3 7 6 8 13 14 9 7 12
    
    Expected output
    Data Set 1:
    2
    
  2. Example 2

    Input
    2
    3 3 1 -4 5 8
    5 3 6
    0 1 2 3 8 7 6
    1 2 1 3 6 1 9 10 13 14 5
    0 2 2 3 7 6 8 13 14 9 7 12
    3 3 1 -4 5 9
    5 3 6
    0 1 2 3 8 7 6
    1 2 1 3 6 1 9 10 13 14 5
    0 2 2 3 7 6 8 13 14 9 7 12
    
    Expected output
    Data Set 1:
    2
    
    Data Set 2:
    1
    
  3. Example 3

    Input
    1
    2 4 3 -2 4 0
    2 2
    0 1 1 2 1 2
    0 1 1 1 1
    0 2 1 2 2 1 3
    0 0 0
    
    Expected output
    Data Set 1:
    0
    
  4. Example 4

    Input
    1
    2 3 5 -100 5 99999
    4 4
    1 1 1 1 1
    1 2 1 2 2 5 6
    1 0 0
    
    Expected output
    Data Set 1:
    3
    
  5. Example 5

    Input
    2
    1 3 1 -1 1 0
    5
    1 0 0
    0 0 0
    0 1 1 0
    1 3 1 -1 1 1
    5
    1 0 0
    0 0 0
    0 1 1 0
    
    Expected output
    Data Set 1:
    3
    
    Data Set 2:
    1