time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
Examples
H. 
6 8 3
1 1 2 2 3 3
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6
Output
2
Input
4 3 3
1 1 2 2
1 2
2 3
3 4
Output
3
Input
4 4 2
1 1 1 2
1 2
2 3
3 1
1 4
Output
0
Input
5 5 2
1 2 1 2 1
1 2
2 3
3 4
4 5
5 1
Output
0