Farshad’s Research


  • محدودیت زمان: ۲ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

Farshad wants to do research on friendship relationships between students of the Shahid Beheshti University, so he has decided to model these relations with a graph. In this graph students are numbered from 11 to nn, every student is represented by a single node, and an edge between node ii and node jj means that student number ii and student number jj are friends with each other. If ii is friend with jj, then jj is also friend with ii, and of course no student can be friend with himself. Farshad is interested in doing research on friendship groups (two students ii and jj are in a friendship group if and only if ii and jj are directly friends with each other or can indirectly connect to each other through friendship links).

Farshad wants to count the number of friendship groups and the number of members each group has. Then HP comes and asks him qq questions about the number of groups that exist in a particular size range. Each question is of the form (l,r)(l, r), which means HP wants to know the number of all groups that have size greater or equal to ll and less than or equal to rr. Help Farshad answer these qq questions.

ورودی🔗

The first line of input contains T, the number of test cases. 1T101≤T≤10 The first line of each test contains three space separated integers n,m,qn, m, q where nn is the number of students, mm is the number of friendship relations and qq is the number of questions HP will ask.

1n,m,q1051 \leq n, m, q \leq 10^5

Then the next mm lines each contain two space separated integers u,vu, v. which means student number uu and student number vv are friends with each other. Then qq lines follow, each containing two space separated integers ll and rr representing the questions HP will ask.

1lrn1 \leq l \leq r \leq n

خروجی🔗

The output should consist of qq lines where line number ii contains the answer to the ii’th question.

مثال‌ها🔗

ورودی نمونه ۱🔗

1
6 4 2
1 2
3 4
4 5
3 5
2 4
3 3
Plain text

خروجی نمونه ۱🔗

2
1
Plain text