Masala #YKN8J2DPKA
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.
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.
Chiqish faylida har bir testlar uchun javobni alohida satrlarda chop eting.
# | input.txt | output.txt |
---|---|---|
1 |
2 3 2 1 3 2 3 4 2 1 2 2 3 |
4 5 |