Slightly weak tests on this problem:
Input:
4 6 4
1 2
1 3
1 4
3 1 4 2 1 1
2 2 2
1 3 1 3
1 2 1 1
1 2 1 1
Output:
3 1 2 5
1 6
1 4
P.S. I am not blaming anyone. Sometimes this kind of thing inevitably happens. I just wanted to let others know that their solutions might be incorrect.