Super Rangers
Swordon is the leader of the Super Rangers, a group of teenagers with attitude! Each Super Ranger owns a Sword, and one of the Swords is called the Dinosword.
A wire connects two different Swords to each other. There are wires connecting the Swords, such that from any Sword, one can reach any other Sword by following a series of wires.
Swordon can merge two Swords and to a Megasword . When he does, every wire attached to or is instead attached to . Note that all wires connecting and now connect to itself, so they become useless and Swordon removes them.
Swordon can also merge a set of Swords to a Megasword. He does this by merging every pair of Swords in , until one Sword remains. It can be shown the result does not depend on the order Swordon chooses.
Consider the diagram below, which shows an example of merging. The set of Swords colored red are merged to a single Megasword. Observe that after the first pair is merged, there are two wires joining the Megasword and the remaining red Sword. After the second pair of Swords is merged, these two wires join the Megasword to itself, and are removed.
The Swords can also transform into Battle Mode. To do this, Swordon divides the Swords into several groups, and merges each group to a single Megasword.
Tita Repulsa, an alien ten times the size of a human, is invading! Swordon needs the Super Rangers to form their Battle Mode. To be effective against Tita Repulsa, the Battle Mode also needs to satisfy the following:
Let be the Dinosword, and the Megasword that replaces . Each Megasword in Battle Mode that is not should be joined to with exactly one wire. There should be no other wires among the Megaswords.
Swordon is only good at wise advice, and not battling aliens. He's not sure which of the Swords is the Dinosword , and instead has a list of possible Dinoswords, . For each possible Dinosword, determine how many ways Swordon can divide the Swords into groups, such that their Battle Mode is effective against Tita Repulsa.
Input Format
The first line contains three integers , , and , the number of Swords, the number of wires connecting the Swords, and the number of possible Dinoswords. The Swords are numbered from to .
The next line contains integers , where each is the number of a possible Dinosword. It is guaranteed that for all .
The next lines each contain two integers and , , representing the th wire joining the Swords numbered and . It is guaranteed that for all .
Constraints
For all subtasks
Subtask 1 (20 points)
Subtask 2 (22 points)
Subtask 3 (38 points)
Subtask 4 (11 points)
Subtask 5 (9 points)
No additional constraints.
Output Format
Print a single line of output containing space-separated numbers, where the th number is the number of ways Swordon can divide the Swords into groups when the Dinosword is Sword number , modulo .
Sample Input 0
4 3 3
1 2 3
1 2
2 3
3 4
Sample Output 0
4 6 6
Explanation 0
There are Swords and wires connecting these Swords, like so: 1-2-3-4
.
If the Dinosword is , there are distinct ways the Swords can be grouped, such that their Battle Mode is effective:
The following ways are invalid:
is not valid, as there would be a wire between the Megasword formed from and the Megasword formed from , neither of which is the Megasword that replaces the Dinosword . Also, the Megasword that replaces would not be joined by any wires to the Megasword that replaces the Dinosword .
is not valid, as there would be two wires between the Megasword formed from and the Megasword formed from , neither of which is the Megasword that replaces the Dinosword . Also, the Megasword that replaces would not be joined by any wires to the Megasword that replaces the Dinosword .
is not valid, as there would be multiple wires joining the Megasword formed from and the Megasword formed from .
If the Dinosword is , there are distinct ways:
If the Dinosword is , there are also distinct ways, not shown here.
Sample Input 1
4 3 6
4 3 2 1 4 3
1 2
1 3
1 4
Sample Output 1
5 5 5 8 5 5
Sample Input 2
6 6 6
1 2 3 4 5 6
1 2
2 3
3 4
4 5
5 6
6 1
Sample Output 2
1 1 1 1 1 1
Explanation 2
Regardless of which Sword is the Dinosword, there is only one way to group the Swords: that is to merge all of them into one Megasword.
xxxxxxxxxx
using namespace std;
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
return 0;
}