Input
5 5 3
1 2 1
2 3 2
1 3 3
3 4 4
1 5 5
3 5
4 5
5 5
Output
2
Input
2 2 3
1 2 2
2 1 3
2 1
2 2
2 3
Output
2