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