12 12
5 1
5 11
1 11
8 11
8 9
5 12
6 9
7 11
9 3
9 10
4 12
10 2
78
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
4 4
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 12
5 5
5 6
5 7
5 8
5 9
5 10
5 11
5 12
6 6
6 7
6 8
6 9
6 10
6 11
6 12
7 7
7 8
7 9
7 10
7 11
7 12
8 8
8 9
8 10
8 11
8 12
9 9
9 10
9 11
9 12
10 10
10 11
10 12
11 11
11 12
12 12

1
3
6
10
15
21
28
36
45
55
65
76
1
3
6
10
15
21
28
36
45
55
66
1
3
6
10
15
21
28
36
45
55
1
3
6
10
15
21
28
36
45
1
3
6
10
15
21
28
36
1
3
6
10
15
21
28
1
3
6
10
15
21
1
3
6
10
15
1
3
6
10
1
3
6
1
3
1

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;

const size_t max_string_length = 100000;
template<class T> struct is_cstr: std::false_type {}; template<int N> struct is_cstr<char[N]> : std::true_type {};
template<typename T> constexpr string formcomm(const T& a) {if constexpr (is_same_v<T, int> || is_same_v<T, size_t>) return "%d"; else if constexpr (is_same_v<T, long long int>) return "%lld"; else if constexpr (is_same_v<T, short int>) return "%hd"; else if constexpr (is_same_v<T, unsigned int>) return "%u"; else if constexpr (is_same_v<T, unsigned long long int>) return "%llu"; else if constexpr (is_same_v<T, unsigned short int>) return "%hu"; else if constexpr (is_same_v<T, char>) return "%c"; else {printf("Type %s non prévu\n", typeid(a).name()); terminate();}}
template<typename T> constexpr string formout(const T& a) {if constexpr (is_same_v<T, float>) return "%.16f"; else if constexpr (is_same_v<T, double>) return "%.16lf"; else if constexpr (is_same_v<T, long double>) return "%.16Lf"; else if constexpr (is_same_v<T, string>) return "%s"; else if constexpr (is_cstr<T>::value) return "%s"; else return formcomm(a);}
template<typename T> const T& addout(const T& a) {return a;} const char* addout(const string& a) {return a.c_str();} 
template<typename... Ts> void out(Ts&&... ts) {printf((formout(ts)+...).c_str(), addout(ts)...);}
template<typename It> void outs(It a, It b, string mid = " ", string fin = "\n") {if (a != b) {out(*a); ++a; for (; a != b; ++a) out (mid, *a);} out(fin);}
template<typename T> void outs(const T& l, string mid = " ", string fin = "\n") {outs(l.begin(), l.end(), mid, fin);}
template<typename T> constexpr string formin(const T& a) {if constexpr (is_same_v<T, float>) return "%f"; else if constexpr (is_same_v<T, double>) return "%lf"; else if constexpr (is_same_v<T, long double>) return "%Lf"; else if constexpr (is_same_v<T, string>) return "%s"; else if constexpr (is_cstr<T>::value) return "%s"; else return formcomm(a);}
template<typename T> constexpr int nstring(const T& a) {if constexpr (is_same_v<T, string>) return 1; else return 0;}
template<typename T> T* addin(T& a, char*& buf, string**& as) {return &a;} char* addin(string& a, char*& buf, string**& as) {char* ob = buf;buf+=max_string_length+1;*as = &a;++as;return ob;} 
template<typename... Ts> void in(Ts&&... ts) {int ns=(nstring(ts)+...);string* as[max(ns,1)];char buf[1+(max_string_length+1)*ns];char* b=buf;string** c=as;
 scanf((formin(ts)+...).c_str(), addin(ts, b, c)...); while (c > as) {--c; b-=max_string_length+1; **c = string(b);}}
template<typename It> void ins(It a, It b) {for (; a != b; ++a) in (*a);} template<typename T> void ins(T& l) {ins(l.begin(), l.end());} 
void inl(char* s) {scanf("%[^\n]", s);} void inl(string& s) {char buf[max_string_length+1]; inl(buf); s = string(buf);}

list<int> browse(const vector<vector<int> >& gr, vector<int>& visited, int i, int cf, vector<tuple<int, int, int> >& cycles)
{
 visited[i] = -1;
 list<int> res;
 for (auto j: gr[i]) if (j != cf)
 {
  if (visited[j] == 0) res.splice(res.end(), browse(gr, visited, j, i, cycles));
  else if (visited[j] == -1) 
  {
   res.push_back(cycles.size());
   cycles.emplace_back(j, j, j);
  }
 }
 for (auto it = res.begin(); it != res.end();)
 {
  auto& [a, b, c] = cycles[*it];
  if (i < b) b = i;
  if (i > c) c = i;
  if (a == i) it = res.erase(it); else ++it;
 }
 visited[i] = 1;
 return res;
}
	
int main()
{
 int n, m;
 in(n, m);
 vector<vector<int> > gr(n);
 for (int i = 0; i < m; ++i)
 {
  int u, v;
  in(u, v); 
  --u; --v;
  gr[u].push_back(v);
  gr[v].push_back(u);
 }
bool dbg = (n == 300000);
 vector<int> visited(n, 0);
 vector<tuple<int, int, int> > cycles;
 for (int i = 0; i < n; ++i) if (visited[i] == 0) browse(gr, visited, i, -1, cycles); else if (visited[i] == -1) {out("panic\n"); return 0;}
 vector<pair<int, int> > forbid;
 for (auto& [u, v, w]: cycles) forbid.emplace_back(v, w);
 sort(forbid.begin(), forbid.end());
 vector<pair<int, int> > fb2;
 if (!forbid.empty()) fb2.push_back(forbid.back());
if (dbg) return 0;
 for (int i = forbid.size() - 2; i >= 0; --i)
  if (forbid[i].second < fb2.back().second) fb2.push_back(forbid[i]);
 int q;
 in(q);
 for (int i = 0; i < q; ++i)
 {
  ll l, r;
  in(l, r);
  --l;
  ll res = 0;
  while (l < r)
  {
   int a = 0; int b = fb2.size();
   while (a + 1 < b)
   {
    int m = (a+b) >> 1;
    if (fb2[m].first >= l) a = m; else b = m;
   }
   int l2 = fb2[a].first;
   int r2 = fb2[a].second;
   if (l2 < l || l2 >= r) {l2 = r-1; r2 = r;}
   if (r2 > r) r2 = r;
   res += ll(l2-l+1)*ll(2*r2-l2-l)/2;
   l = l2+1;
  }
  out(res, "\n");
 }
 return 0;
}
