Counting Valid DFS Orders

Given an undirected graph \(G=(V,E)\) with \(n=|V|\) vertices and \(m=|E|\) edges, where the vertices are numbered from 1 to \(n\), a depth‐first search (DFS) is performed starting from vertex 1. During the DFS process, when a new vertex is visited for the first time, it is recorded. Thus, after some time the DFS process has visited exactly \(k\) distinct vertices and the order in which these vertices were first discovered forms a sequence (a permutation of \(k\) numbers). However, note that not every permutation of \(k\) distinct numbers can arise as a DFS order.

Assume that the DFS is implemented using recursion (or an equivalent stack-based method) and at each step, if there are several unvisited neighbors available, the algorithm may choose any one of them arbitrarily. In other words, the DFS order is affected by the order in which the neighbors are explored. For a fixed DFS tree obtained during the process, different orders of exploring the children of each vertex will yield different DFS orders. In fact, if in the DFS tree each vertex \(v\) has \(c_v\) children, then the number of DFS orders that yield that DFS tree is

[ \prod_{v \text{ in the DFS tree}} (c_v)! ]

In this problem, you are given the whole graph and the current DFS sequence of the \(k\) visited vertices (which is guaranteed to be a valid DFS order for some DFS tree). Your task is to compute the number of different DFS orders (i.e. different neighbor‐exploration orders) that could have produced this partial DFS order.

Reconstructing the DFS Tree

You are also given the DFS sequence \(a_1,a_2,\dots,a_k\) (with \(a_1=1\)). The DFS tree can be uniquely recovered from this sequence by using the following simulation:

1. Initialize an empty stack and push \(a_1\) onto it.
2. For each subsequent vertex \(a_i\) (\(2 \le i \le k\)):
   1. While the stack is nonempty and there is no edge between the vertex at the top of the stack and \(a_i\), pop from the stack.
   2. The vertex now on the top of the stack is the parent of \(a_i\) in the DFS tree. Increase the child count for that parent by 1.
   3. Push \(a_i\) onto the stack.

After processing all \(k\) vertices, let \(c_v\) be the number of children of vertex \(v\) in the reconstructed DFS tree (for vertices that appear in the DFS sequence). Then the answer is

[ \text{answer} = \prod_{v \text{ in the DFS sequence}} (c_v)! ]

You may assume that the DFS sequence given is valid.

inputFormat

The input consists of several parts:

1. The first line contains three integers \(n\), \(m\) and \(k\): the number of vertices, the number of edges, and the number of vertices visited so far, respectively.
2. Then \(m\) lines follow, each containing two integers \(u\) and \(v\) (1-based indices), indicating there is an undirected edge between vertices \(u\) and \(v\).
3. The last line contains \(k\) distinct integers: \(a_1,a_2,\dots,a_k\) representing the DFS order of the visited vertices. It is guaranteed that \(a_1=1\).

outputFormat

Output a single integer representing the number of different DFS orders (i.e. different valid neighbor‐exploration orders) that correspond to the given DFS sequence. Note that for each vertex in the DFS tree, different orders of exploring its children yield different DFS orders. Factorials are taken in the usual sense (with \(0! = 1\)).

sample

5 4 5
1 2
1 3
2 4
2 5
1 2 4 5 3

4