+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- 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 $1$ to $n$, every student is represented by a single node, and an edge between node $i$ and node $j$ means that student number $i$ and student number $j$ are friends with each other. If $i$ is friend with $j$, then $j$ is also friend with $i$, and of course no student can be friend with himself. Farshad is interested in doing research on friendship groups (two students $i$ and $j$ are in a friendship group if and only if $i$ and $j$ 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 $q$ questions about the number of groups that exist in a particular size range. Each question is of the form $(l, r)$, which means HP wants to know the number of all groups that have size greater or equal to $l$ and less than or equal to $r$. Help Farshad answer these $q$ questions. # ورودی The first line of input contains T, the number of test cases. $$1≤T≤10$$ The first line of each test contains three space separated integers $n, m, q$ where $n$ is the number of students, $m$ is the number of friendship relations and $q$ is the number of questions HP will ask. $$1 \leq n, m, q \leq 10^5$$ Then the next $m$ lines each contain two space separated integers $u, v$. which means student number $u$ and student number $v$ are friends with each other. Then $q$ lines follow, each containing two space separated integers $l$ and $r$ representing the questions HP will ask. $$1 \leq l \leq r \leq n$$ # خروجی The output should consist of $q$ lines where line number $i$ contains the answer to the $i$’th question. # مثال‌ها ## ورودی نمونه ۱ ``` 1 6 4 2 1 2 3 4 4 5 3 5 2 4 3 3 ``` ## خروجی نمونه ۱ ``` 2 1 ```

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 $1$ to $n$ , every student is represented by a single node, and an edge between node $i$ and node $j$ means that student number $i$ and student number $j$ are friends with each other. If $i$ is friend with $j$ , then $j$ is also friend with $i$ , and of course no student can be friend with himself. Farshad is interested in doing research on friendship groups (two students $i$ and $j$ are in a friendship group if and only if $i$ and $j$ 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 $q$ questions about the number of groups that exist in a particular size range. Each question is of the form $(l, r)$ , which means HP wants to know the number of all groups that have size greater or equal to $l$ and less than or equal to $r$ . Help Farshad answer these $q$ questions.

ورودی🔗

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

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

Then the next $m$ lines each contain two space separated integers $u, v$ . which means student number $u$ and student number $v$ are friends with each other. Then $q$ lines follow, each containing two space separated integers $l$ and $r$ representing the questions HP will ask.

$1 \leq l \leq r \leq n$

خروجی🔗

The output should consist of $q$ lines where line number $i$ contains the answer to the $i$ ’th question.

مثال‌ها🔗

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

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

2
1