C. Цагийн хуваарь

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Берландын Их Сургууль шинэ семестер эхлэхэд шинэ хуваарь гаргадаг. Энэ цагийн хуваарийн дагуу $31$-р тэнхимд $n$ грүпп хичээлтэй байдаг. Групп болгоны хичээл эхлэх ба дуусах цаг нь мэдэгдэж байгаа. Зарим грүппийн хичээлийн цаг нь давхцсанаас болж бүх хичээлийг хичээллүүлэх боломжгүй болжээ. Хэрвээ нэг группын хичээл дуусах агшинд бусад группын хичээл орж эхэлвэл үүнийг давхцахгүй гэж үзнэ.

Декан үлдсэн бүлгийн хичээлээс ямар ч гэсэн $2$ нь давхцаж байхгүйгээр заримыг нь цуцлахаар болжээ. Та үүнийг шийдвэрлэх бүх замыг олно.

Оролт

Эхний мөрөнд группын тоо $n$ ($1 ≤ n ≤ 5000$). Дараагийн $n$ мөрөнд групп болгоны хичээлийн эхлэх цаг ба төгсөх цаг $l_i$, $r_i$ ($1 ≤ l_i < r_i ≤10^6$). Энд ямар ч грүппийн хичээлийн цаг давхцаагүй байж болно (1-р жишээг харна уу).

Гаралт

Хэдэн янзаар давхцахгүй хичээлийн хуваарь үүсгэж болох боломжийн тоо болох $k$-г хэвлэ. Дараагийн мөрөнд $k$ ширхэг тоо байх ба энэ нь хичээл хасах группын дугаар байна. Бүлгүүдийг эхнээс нь нэгээс эхэлж дугаарласан гэж үзнэ. Гаралтаа өсөхөөр эрэмбэлж хэвлэнэ.

Орчуулсан: Itgel

Жишээ тэстүүд

Оролт
3
3 10
20 30
1 3
Гаралт
3
1 2 3 
Оролт
4
3 10
20 30
1 3
1 39
Гаралт
1
4 
Оролт
3
1 5
2 6
3 7
Гаралт
0
Сэтгэгдлүүдийг ачааллаж байна...