2 shunfurh shunfurh 于 2017.11.14 17:46 提问

Visit relatives

Problem Description
When Wiskey return home, many relatives he need to visit, and he will buy some gifts before he visit his relatives. There is a map which has N places; Wiskey's house is labeled 0. He has T tasks which from u to v, it mean Wiskey could go to v when he bought a gift at u before.
Wiskey always start at 0, and must end with 0.
Tell him how many minimum total places he went when he finished all tasks.

Input
First line will contain one integer mean how many cases will follow by; the number of cases wills less than 20.
In each case will contain three integers N means the number of places, M roads and T tasks. (1 <= N <= 20, 0 <= M <= 100, 0 <= T <= 5).
First, M roads will be follow; the road is bi-connected.
Second, T tasks will be follow; you are remember the u must went earlier than v, then what makes the task will be finished.

Output
Print the minimum total number of places he went.
If Wiskey can't finish all tasks, please print -1.

Sample Input
1
7 11 5
0 1
0 2
1 2
1 4
0 3
3 4
4 6
2 6
6 5
3 5
4 5
1 2
1 3
2 0
1 4
5 3

Sample Output
7

Csdn user default icon
上传中...
上传图片
插入图片