SEAPORTS Cầu cảng

Một cảng biển có 𝑚 cầu cảng để tiếp nhận các tàu cập bến. Tại một thời điểm, mỗi cầu cảng chỉ có thể  tiếp nhận không quá 1 tàu. Ban đầu các cầu cảng đều trống và có 𝑛 tàu xin  đăng ký cập bến, tàu thứ 𝑖  muốn đậu ở  cảng từ  ngay sau thời điểm 𝑠_𝑖 tới hết thời điểm 𝑓_𝑖. Có thể  coi thời gian tàu thứ 𝑖  muốn đậu ở cảng là một khoảng (𝑠_𝑖, 𝑓_𝑖] trên trục thời gian. Tàu đã vào cầu cảng nào thì sẽ đậu ở đó trong suốt thời gian nằm cảng.

Yêu cầu: Hãy cho biết với 𝑚 cầu cảng đã cho, có thể tiếp nhận tối đa bao nhiêu tàu và chỉ ra lịch trình tiếp nhận tại mỗi cầu cảng.

Input

• Dòng 1: Chứa hai số nguyên dương 𝑚, 𝑛 ≤ 10⁵
• 𝑛 dòng tiếp theo, dòng thứ 𝑖  chứa hai số nguyên 𝑠_𝑖, 𝑓_𝑖 (0 ≤ 𝑠_𝑖< 𝑓_𝑖≤ 10⁵).

Output

• Dòng 1: Ghi số lượng tàu được tiếp nhận phục vụ
• Dòng 2: Ghi 𝑛 số  nguyên, số  thứ 𝑖  là số  hiệu cầu  cảng  sẽ  tiếp nhận tàu thứ 𝑖  trong trường hợp tàu thứ 𝑖  được tiếp nhận, còn nếu tàu thứ 𝑖  không được tiếp nhận thì số thứ 𝑖  là 0.

Input	Output
2 5 0 3 3 5 0 2 2 5 1 4	4 1 1 2 2 0

Subtask:

10% test ~ 4 test có n ≤ 20.

45% test ~ 18 test có n ≤ 5000

45% test ~ 18 test có n ≤ 10⁵.

Các số trên một dòng của Input/Output files được/phải ghi cách nhau ít nhất một dấu cách.