Post Office Investigation

Example

Input

8 8 1 2 1 3 2 4 2 5 2 8 3 5 3 6 4 7 1000 100 100 10 10 10 1 1 3 2 8 6 2 4 7 2 7 8

Output

1000 10 100

inputFormat

Input

8 8 1 2 1 3 2 4 2 5 2 8 3 5 3 6 4 7 1000 100 100 10 10 10 1 1 3 2 8 6 2 4 7 2 7 8

outputFormat

Output

1000 10 100

样例

8 8
1 2
1 3
2 4
2 5
2 8
3 5
3 6
4 7
1000
100
100
10
10
10
1
1
3
2 8 6
2 4 7
2 7 8

1000
10
100