Inversion sorting

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
The Aa'ugld alphabet consists of M letters, which we'll denote by integers from 1 to M in alphabetical order  the smaller number a letter has, the earlier it appears in the alphabet. Since the author of this alphabet wasn't very creative, many letters can be transformed to other ones using some simple operations, which we'll call "inversions".
You're given a list of possible operations. The list isn't exhaustive, since any two inversions can be combined to produce a new inversion. Specifically, if there is an inversion that transforms a letter x to a letter y and an inversion that transforms the letter y to a letter z, you may assume that there's also an inversion that transforms the letter x to the letter z. In short, "inversion" operations are transitive.
Combining any inversion with itself produces identity  an operation that transforms any letter to itself. (That's where the name "inversion" comes from  an operation that's its own inverse.) Therefore, if there's an inversion that transforms a letter x to a letter y, then there's also an inversion that transforms the letter y to the letter x.
There's a long word W with N letters. You should transform some of these letters to other ones in order to make the letters of W sorted in alphabetical order. Is it possible at all? If it is, what's the minimum number of letters that should be transformed?
Input
 The first line of the input contains an integer T  the number of test cases.
 The first line of each test case contains three integers M, K and N.
 The following K lines each contain two integers x and y, denoting an inversion that transforms letter x to letter y.
 The last line of each test case contains N integers a_{i}  letters of the word W.
Output
For each test case, output a single line containing 1 if it's impossible to make the letters of W sorted in alphabetical order. Otherwise, output the smallest number of letters that need to be transformed to achieve that.
Constraints
 1 ≤ T ≤ 10
 1 ≤ N ≤ 200000
 0 ≤ K ≤ M(M1)/2
 1 ≤ x,y ≤ M
 all unordered pairs (x,y) will be distinct
 1 ≤ a_{i} ≤ M
Subtask 1 (18 points):
 1 ≤ M ≤ 10
 1 ≤ N ≤ 20
Subtask 2 (60 points):
 1 ≤ M ≤ 50
 1 ≤ N ≤ 20000
Subtask 3 (22 points):
 1 ≤ M ≤ 200
 1 ≤ N ≤ 200000
Example
Input: 2 3 3 3 1 2 2 3 3 1 3 2 1 3 1 2 2 3 2 1 Output: 2 1
Explanation
Example case 1. It's possible to transform the first letter to 1 and the last letter to 2. The resulting word has letters 1 2 2.
Example case 2. This word can only be transformed to 2 1 or 3 1.
Author:  xellos0 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/CARLOS 
Tags  april15, dynamicprogramming, easymedium, prefixminimum, xellos0 
Date Added:  25012015 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 