Nghệ thuật

Trong một chuyến đi đến một thành phố xa lạ, bạn phát hiện rằng tại đây đang diễn ra \(N\) sự kiện nghệ thuật hiện đại, được đánh số từ \(1\) đến \(N\). Sự kiện thứ \(i\) bắt đầu lúc \(S_i\) và kết thúc lúc \(E_i\).

Bạn muốn tham gia các sự kiện này bằng cách chọn một sự kiện bắt đầu \(s\) và một sự kiện kết thúc \(e\). Trong thời gian tham gia, bạn luôn ở lại đến hết sự kiện hiện tại, sau đó lập tức chuyển đến một sự kiện khác đang diễn ra (đang mở cửa).

Bạn có thể chuyển từ sự kiện \(i\) sang sự kiện \(j\) nếu và chỉ nếu \(S_j \le E_i \le E_j\).

Hãy trả lời \(Q\) truy vấn, mỗi truy vấn hỏi: số lần chuyển sự kiện ít nhất để đi từ sự kiện \(s_i\) đến sự kiện \(e_i\). Nếu không thể đi từ \(s_i\) đến \(e_i\), hãy in impossible.

\InputFile

• Dòng đầu chứa hai số nguyên \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)) --- số lượng sự kiện và số lượng truy vấn.
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(S_i, E_i\) (\(1 \le S_i < E_i \le 10^9\)) --- thời gian bắt đầu và kết thúc của sự kiện thứ \(i\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(s_i, e_i\) (\(1 \le s_i, e_i \le N\)).

\OutputFile
Với mỗi truy vấn, in ra số lần chuyển sự kiện ít nhất (số nguyên), hoặc dòng impossible nếu không thể.

\Scoring

• Subtask 1 (10 điểm): Mỗi sự kiện có thể chuyển đến nhiều nhất một sự kiện khác.
• Subtask 2 (10 điểm): \(N \le 1000\), \(Q \le 100\).
• Subtask 3 (15 điểm): \(N \le 5000\).
• Subtask 4 (15 điểm): \(Q \le 100\).
• Subtask 5 (20 điểm): Không có sự kiện nào bị bao toàn bộ trong một sự kiện khác, tức là không tồn tại \(i \ne j\) sao cho \(S_i \le S_j < E_j \le E_i\).
• Subtask 6 (30 điểm): Không có ràng buộc gì thêm.

\Examples

\beginexample
\exmp
5 2
1 3
2 4
4 7
7 9
3 7
1 4
3 2

2
impossible

\endexample

\Note
Ở truy vấn đầu tiên, bạn có thể đi từ sự kiện 1 \(\rightarrow\) 5 \(\rightarrow\) 4, mất 2 lần chuyển.
Ở truy vấn thứ hai, không thể từ sự kiện 3 đến sự kiện 2 vì sự kiện 2 kết thúc trước khi sự kiện 3 bắt đầu.

\endproblem