Warm summer night. Vito and his friend, Karlo, are lying in a forest clearing and watching the stars. Suddenly, Vito exclaims "Karlo, look! The trees around us are changing colors!" "Wooow so colorful" said Karlo, amazed. Indeed, the tree branches in the forest started to change colors.
Fascinated by the colorful trees, Vito and Karlo noticed a couple of facts about
them. Each of the trees they are looking at can be represented as a tree graph,
i.e. an undirected graph in which there exists a unique path between each pair
of nodes. The trees they are looking at have the property that each edge of
the tree is colored in one of different colors. Some of the paths on the tree
are colorful, meaning that such a path contains edges of at least two different
colors.
Morning has arrived and the tree magic is now lost. In order to relive this experience, Vito and Karlo ask you to solve the following problem:
Given a tree and
pairs of nodes on the tree, determine the number of different colorings of the tree edges so that each of the
paths determined by the
pairs of nodes is colorful.
Since this number can be very large, output it modulo .
Input Specification
The first line contains three positive integers ,
, and
, the
number of nodes in the tree, the number of path required to be colorful and the number of possible colors
for the tree branches, respectively.
The of the next
lines contains a pair of positive integers
and
, representing
an edge of the tree.
The of the next
lines contains a pair of positive integers
and
, the labels of the
endpoints of the paths which are required to be colorful. The nodes
and
are not neighboring.
Output Specification
In the only line, print the number of ways to color the tree edges so that each of the given paths is
colorful, modulo
.
Constraints
Subtask | Points | Constraints |
---|---|---|
1 | 10 | |
2 | 15 | |
3 | 10 | Each tree edge belongs to at most one of the |
4 | 10 | |
5 | 65 | No additional constraints. |
Sample Input 1
3 1 2
1 2
2 3
1 3
Sample Output 1
2
Explanation for Sample Output 1
The tree consists of only two edges, both part of a colorful path between the nodes and
. So, the two
edges must have a different color. One such coloring is obtained by coloring the edge
in color
, and
in color
, while the other is obtained by switching these color so that
has color
, and
has
color
.
Sample Input 2
4 3 2
1 2
2 3
4 2
1 4
1 3
4 3
Sample Output 2
0
Sample Input 3
4 3 3
1 2
2 3
4 2
1 4
1 3
4 3
Sample Output 3
6
Comments