A. Prologue to Penacony
time limit per test
3 s.
memory limit per test
512 MB
input
standard input
output
standard output

This is an easy version of CF1996G : Penacony

You can submit your $$$O(N \cdot M)$$$ solution here. You should get a TLE6 verdict. Make sure that it's not WA.

Examples
Input
7
8 3
1 8
2 7
4 5
13 4
1 13
2 12
3 11
4 10
10 2
2 3
3 4
10 4
3 8
5 10
2 10
4 10
4 1
1 3
5 2
3 5
1 4
5 2
2 5
1 3
Output
4
7
2
7
2
3
3