[solution] Spooky Sequences solution codechef

Problem solution codechef

“I am not a witch. I’m your wife.”
– Valerie, The Princess Bride

Once upon a time, in a distant land, a mischievous witch spied on a group of people who were enjoying their time together.

Enveloped by a dark desire, she resolved to put an end to their merry gatherings and kill all  people.

There are  people, and the witch knows that the -th of them has a strength of ��.
The witch also knows of  friendships, each between two people. Friendship is transitive, that is, if  and  are friends and  and  are friends, then  and  are also friends.

The witch wants to kill all these people in a particular sequence known as a spooky sequence.

A sequence  is called a spooky sequence if it satisfies the following properties:

  •  contains  distinct integers, each between 1 and .
    That is,  is a linear order of the  people.
  • For any 1≤�<�≤�, if �� and �� are friends, then ���≤��� should hold.
    That is, for any two friends, one with strictly higher strength cannot appear earlier in the sequence than the other.

Find the total number of spooky sequences. The answer can be large, so print it modulo 109+7.

Input Format

  • The first line of input will contain a single integer , denoting the number of test cases.
  • Each test case consists of multiple lines of input.
    • The first line of each test case contains two space-separated integers  and  — the number of people and number of friendships, respectively.
    • The next  lines describe the friendships. The -th of these  lines contains two space-separated integers �� and ��, denoting a friendship between �� and ��.
    • The last line contains  space-separated integers �1,�2,…,�� — the strengths of the people.

Output Format

For each test case, output on a new line the number of spooky sequences, modulo 109+7.

Constraints

  • 1≤�≤2⋅104
  • 1≤�≤2⋅105
  • 0≤�≤min⁡(2⋅105,�⋅(�−1)/2)
  • 1≤��,��≤�
  • ��≠�� for each 1≤�≤�.
  • Each unordered pair (��,��) appears at most once in a testcase.
  • 1≤��≤109
  • The sum of  over all test cases won’t exceed 2⋅105.
  • The sum of  over all test cases won’t exceed 2⋅105.

Sample 1:

Input

Output

2
5 5
1 2
2 3
3 4
4 2
3 1
10 12 15 20 15
5 2
2 3
4 5
6 4 4 3 1
5
60

Explanation:

Test case 1: Each pair among {1,2,3,4} are friends, while 5 is not friends with anyone else. Taking into account the strength condition for the group of 4, there are five spooky sequences:
[5,1,2,3,4]
[1,5,2,3,4]
[1,2,5,3,4]
[1,2,3,5,4]
[1,2,3,4,5]

Test case 2: 2 and 3 are friends, 4 and 5 are friends, and 1 is not a friend of anyone else.
So, in any ordering:

  • �2=�3, so the order of 2 and 3 doesn’t matter (even though they are friends).
  • 4 should appear after 5, since �4>�5.
  • There are no further constraints.

It can be verified that there are 60 sequences satisfying this.

Leave a Comment