input

5 100
5 4
2 4
1 4
3 1
1 2
1 4
2 5
2 1
1 3
1 3
1 4
1 2
2 5
2 3
2 2
2 5
1 5
1 1
2 1
1 2
2 3
2 4
1 1
2 1
2 2
2 5
2 1
2 4
1 4
2 5
1 5
1 1
2 4
2 2
2 3
1 1
2 3
2 3
2 3
1 4
2 1
1 2
1 5
1 2
1 5
2 5
2 5
1 4
1 5
1 5
1 1
2 2
2 3
1 1
2 4
1 3
1 2
1 5
2 3
2 3
2 4
2 2
1 3
1 2
2 3
2 3
2 5
1 5
1 2
1 5
1 5
2 2
2 5
2 5
1 3
2 2
1 2
2 2
2 5
2 2
1 4
1 3
1 4
2 2
1 2
1 2
1 5
1 2
2 4
1 5
2 4
1 4
2 1
2 4
2 4
2 2
2 4
1 2
2 4
1 5
2 3
2 2
1 4
2 4