E. Шидтэн

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

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

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

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

Эрд дээр үед А гэгч нэгэн шидтэн байжээ. Нэгэн өдөр В гэгч сайн залуу түүн дээр ирж ирээдүйг нь зөгнөн хэлэхийг гуйжээ. Шидтэн шидэт бөмбөлөг рүүгээ харан ингэж хэлэв. Та удахгүй урьд хожид байгаагүй хамгийн үзэсгэлэнтэй гүнжтэй учирч гэрлэх юм байна. Тэгээд тэрээр хуудас цаас авч $n$ цэгүүд зураад заримыг нь сегментээр холбов. Сегмент бүр аль нэг цэгээс эхлэх ба өөр нэгэн цэгт дуусна.

Ийнхүү зурсны дараа шидтэн түүнээс цаасан дээрх нэг сегментийг устгахыг хүсчээ. Тэрээр цэг бүрийг улаан, цэнхэрээр ээлжлэн будаж дуусахад ижил өнгөөр будагдсан цэгтэй сегмент байхгүй байна. Хэрэв шидтэн үүнийг хийж чадвал тэр залуугийн амьдралын талаар ярьсан түүний зөгнөл үнэн байх юм. В мэдээж хамгийн үзэсгэлэнтэй гүнжтэй гэрлэхийг хүсч байгаа учир та бүхнээс тусламж гуйж байгаа юм.

Түүнийг гүнжтэй уулзахад туслах бүх сегментүүдийг ол.

Оролт

Эхний мөр нь нийт цэгүүдийн тоог харуулсан $n$, нийт ($1 ≤ n ≤ 10^{4}, 0 ≤ m ≤ 10^{4}$) сегментийн тоог харуулсан $m$ гэсэн хоёр бүхэл тоог агуулна. Дараагийн $m$ мөрүүд нь сегментийн тодотгол агуулсан байна. Тодотгол нь зайгаар тусгаарлагдсан өөр өөр хоёр тоог агуулах ба энэ нь тус сегментээр холбогдсон цэгүүдийг илэрхийнэ. Тодотголд сегментүүд хоёр удаа давхардахгүй.

Гаралт

Эхний мөр $k$ гэсэн тоонууд агуулах ба эдгээр нь хариултанд байгаа сегментийн тоог илэрхийлж байна. Хоёр дахь мөрөнд $k$ гаралтын зайгаар тусгаарлагдсан тоонууд нь сегментийн индексүүдийг өсөх дарааллаар илэрхийлнэ. Индекс бүр зөвхөн нэг удаа гаралт болох ёстой. Сенментүүд нь оролтын дарааллаараа 1-ээс эхлэн эрэмбэлэгдэнэ.

Орчуулсан: Энхгэрэл

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

Оролт
4 4
1 2
1 3
2 4
3 4
Гаралт
4
1 2 3 4 
Оролт
4 5
1 2
2 3
3 4
4 1
1 3
Гаралт
1
5 
Сэтгэгдлүүдийг ачааллаж байна...