Input
6 0 6
2 1 2
2 3 4
2 5 6
2 3 2
2 5 3
1 1
Output
4