D. Холбогдсон бүрэлдэхүүн хэсгүүд

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

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

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

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

Бид аль хэдийн Поликарпус нэгэн том байгууллагад систем удирдагчаар ажиллаж байгааг мэдэж байв. Тэнд байх компьютерын сүлжээ нь $n$ ширхэг компьютерууд болон хос компьютеруудыг холбох $m$ ширхэг кабелаас бүрдэнэ. Өөрөөр хэлбэл компьютерын сүлжээ нь $n$ зангилааны цэг болон $m$ ирмэг бүхий чиглэлгүй графаар дүрслэгдэж болох юм. Компьютеруудыг 1-ээс эхлэн $n$ хүртэлх бүхэл тоонуудаар дугаарлая. Кабелуудыг 1-ээс эхлэн $m$ хүртэлх бүхэл тоонуудаар дугаарлая.

Поликарпус-д нэгэн чухал даалгавар өгөгджээ. Тэрээр өөрийн байгууллагын сүлжээний найдвартай байдлыг шалгахаар болжээ. Үүний тулд Поликарпус компьютерын сүлжээнд $k$ ширхэг туршилт явуулах ба $i$-дахь туршилт нь дараах байдалтай явагдана:

  1. $l_{i}$-аас $r_{i}$ хүртэлх (эдгээр нь өөрсдөө мөн салгагдана) дугаартай кабелуудыг түр зуур салгах ба бусад кабелууд нь холбогдсон хэвээр байх юм.
  2. Уг мөчид компьютерын сүлжээг тодорхойлж буй граф дахь холбогдсон бүрэлдэхүүн хэсгүүдийн тоог тоолно.
  3. $l_{i}$-аас $r_{i}$ хүртэлх дугаартай салгагдсан кабелуудыг дахин холбох ба энэ нь анхны сүлжээг сэргээнэ гэсэн үг юм.

Поликарпус-д туслан бүх туршилтыг гүйцэтгэн тус бүрийнх нь хувьд тухайн туршилтын явцад компьютерын сүлжээг тодорхойлж буй граф дахь холбогдсон бүрэлдэхүүн хэсгүүдийн тоог хэвлэж өгнө үү. Тусгаарлагдсан орой нь нэг бүрэлдэхүүн хэсэг гэж тооцогдоно.

Оролт

Эхний мөрөнд харгалзан компьютерын тоо болон кабелын тоог илэрхийлэх зайгаар тусгаарлагдсан 2 бүхэл тоо $n$, $m$ $(2 ≤ n ≤ 500; 1 ≤ m ≤ 10^{4})$ өгөгдөнө.

Дараагийн $m$ мөрөнд кабелуудын тайлбар өгөгдөнө. $i$-дахь мөрөнд зайгаар тусгаарлагдсан хос бүхэл тоо $x_{i}$, $y_{i}$ $(1 ≤ x_{i}, y_{i} ≤ n; x_{i} ≠ y_{i})$ өгөгдөх ба эдгээр нь $i$-дахь кабелаар холбогдож буй компьютеруудын дугаарыг илэрхийлнэ. Хос компьютер нь олон тооны кабелуудаар холбогдож болохыг анхаарна уу.

Дараагийн мөрөнд туршилтын тоо болох $k$ $(1 ≤ k ≤ 2*10^{4})$ өгөгдөнө. Дараагийн $k$ мөрөнд туршилтуудын тайлбар өгөгдөнө. $i$-дахь мөрөнд зайгаар тусгаарлагдсан бүхэл тоонууд $l_{i}$, $r_{i}$ $(1 ≤ l_{i} ≤ r_{i} ≤ m)$ өгөгдөх ба эдгээр нь $i$-дахь туршилтын үеэр Поликарпус-ын салгах кабелуудын дугааруудыг илэрхийлнэ.

Гаралт

$k$ ширхэг тоо хэвлэх ба $i$-дахь тоо нь $i$-дахь туршилтын явцад компьютерын сүлжээг тодорхойлж буй граф дахь холбогдсон бүрэлдэхүүн хэсгүүдийн тоо байна.

Орчуулсан: Баатархүү

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

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