Masala #YKN8J2DPKA

Xotira 32 MB Vaqt 2000 ms
14

Hoshimjon va do'stlari #1

Hoshimjon uyiga \(n\) ta do'stini taklif qildi. Stol atrofidagi o'rindiqlar \(1,2,...,n\) tartibda raqamlangan bo'lib Hoshimjonning do'stlari o'rindiqlarga joylashib olishdi. 

Unda jami \(m\) ta bir birini tanimaydigan jufliklar ro'yxati mavjud. Ushbu ro'yxatga kiritilmagan har qanday juftlik do'stlar bir birini taniydi. Siz shunday \([a,a+1,a+2,...,b](1\leq a\leq b\leq n)\) segmintlarni topingki ushbu segmintdagi barcha do'stlar bir birini tanisin, bunday segmintdagi do'stlar yaxshi do'stlar segminti hisoblanadi.

Sizning vazifangiz Hoshimjonning do'stlari joylashgan stolda jami bo'lib nechta yaxshi do'stlar segminti mavjudligini aniqlashdan iborat.


Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrda testlar soni \(t(1\leq t\leq 20000)\) beriladi. Kiyingi satrlarda \(t\) ta test beriladi, har bir test uchun \(n,m(2\leq n\leq 100000,0\leq m\leq min(2n,n(n-1)/2))\)mos ravishda Hoshimjonning do'stlari soni va o'zaro bir birini tanimaydigan juftliklar(barcha testlar uchun \(t+m_i\leq 10^6, 1\leq i\leq t\)). Kiyingi \(m\) ta satrda \(u_i,v_i(1\leq u_i, v_i\leq n, u_i \neq v_i)\) o'zaro bir birini tanimaydigan juftliklar.


Chiquvchi ma'lumotlar:

Chiqish faylida har bir testlar uchun javobni alohida satrlarda chop eting.


Misollar
# input.txt output.txt
1
2
3 2
1 3
2 3
4 2
1 2
2 3
4
5