Sample Input 1

5
1 2
2 5
2 4
5 3

Sample Output 1

1
4
2
2
3

Sample Input 2

10
1 3
1 5
5 2
5 9
9 7
9 10
6 2
4 2
8 4

Sample Output 2

3
8
2
4
8
2
2
2
4
1

Subtask

• 25% số điểm có ~N \le 5~;
• 25% số điểm có ~N \le 1000~;
• 50% số điểm không có ràng buộc gì thêm.