You are given an undirected graph with n vertices. There are no edge-simple cycles with the even length in it. In other words, there are no cycles of even length that pass each edge at most once. Let's enumerate vertices from 1 to n. 

You have to answer q queries. Each query is described by a segment of vertices [l; r], and you have to count the number of its subsegments [x; y] (l ≤ x ≤ y ≤ r), such that if we delete all vertices except the segment of vertices [x; y] (including x and y) and edges between them, the resulting graph is bipartite.

Input

The first line contains two integers n and m (1 ≤ n ≤ 3·105, 1 ≤ m ≤ 3·105) — the number of vertices and the number of edges in the graph.

The next m lines describe edges in the graph. The i-th of these lines contains two integers ai and bi (1 ≤ ai, bi ≤ n; ai ≠ bi), denoting an edge between vertices ai and bi. It is guaranteed that this graph does not contain edge-simple cycles of even length.

The next line contains a single integer q (1 ≤ q ≤ 3·105) — the number of queries.

The next q lines contain queries. The i-th of these lines contains two integers li and ri (1 ≤ li ≤ ri ≤ n) — the query parameters.

Output

Print q numbers, each in new line: the i-th of them should be the number of subsegments [x; y] (li ≤ x ≤ y ≤ ri), such that the graph that only includes vertices from segment [x; y] and edges between them is bipartite.

Examples

Input

6 6
1 2
2 3
3 1
4 5
5 6
6 4
3
1 3
4 6
1 6


Output

5
5
14


Input

8 9
1 2
2 3
3 1
4 5
5 6
6 7
7 8
8 4
7 2
3
1 8
1 4
3 8


Output

27
8
19

Note

The first example is shown on the picture below:

<image>

For the first query, all subsegments of [1; 3], except this segment itself, are suitable.

For the first query, all subsegments of [4; 6], except this segment itself, are suitable.

For the third query, all subsegments of [1; 6] are suitable, except [1; 3], [1; 4], [1; 5], [1; 6], [2; 6], [3; 6], [4; 6].

The second example is shown on the picture below:

<image>
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class C
{
	static int n, m, vid;
	static ArrayList<Integer>[] adj;
	static int[] f, cycle, vis, depth;
	static long[] set; static int sInd;
	
	public static void main(String[] args) throws IOException
	{
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		
		n = sc.nextInt();
		m = sc.nextInt();
		
		set = new long[m];
		f = new int[n];
		cycle = new int[n];
		vis = new int[n];
		vid++;
		adj = new ArrayList[n];
		depth = new int[n];
		for (int i = 0; i < adj.length; i++)
			adj[i] = new ArrayList<Integer>();
		
		for (int i = 0; i < m; i++)
		{
			int a = sc.nextInt()-1;
			int b = sc.nextInt()-1;
			adj[a].add(b);
			adj[b].add(a);
		}
		
		
		dfs(0,-1,1);
		
		Arrays.sort(set);
		
		vid++;
		for (int i = 0; i < n; i++)
		{
			if(vis[i] != vid)
			{
				mx = i;
				maxCycle(i);
				if(mx == i)
					cycle[i] = n-1;
				else
					cycle[i] = mx-1;
			}
			else
			{
				cycle[i] = n-1;
			}
		}
		
		buildF();
		
		int q = sc.nextInt();
		
		int N = 1; while(N < n) N <<= 1; //padding
		
		int[] in = new int[N + 1];
		
		SegmentTree tree = new SegmentTree(in);
		
//		ArrayList<Pair>[] queries = new ArrayList[n]; 
		int[][][] queries = new int[n][2][];
		int[] ql = new int[q];
		int[] qr = new int[q];
		int[] cnt = new int[n];
		long[] ans = new long[q];
		for (int i = 0; i < q; i++)
		{
			int l = sc.nextInt()-1;
			ql[i] = l;
			qr[i] = sc.nextInt()-1;
			cnt[l]++;
		}
		for (int i = 0; i < n; i++)
		{
			queries[i][0] = new int[cnt[i]];
			queries[i][1] = new int[cnt[i]--];
		}
		
		for (int i = 0; i < q; i++)
		{
			int l = ql[i];
			int r = qr[i];
			queries[l][0][cnt[l]] = r;
			queries[l][1][cnt[l]--] = i;
		}
		
		for (int i = n-1; i >= 0; i--)
		{
			tree.update_range(i+1, f[i]+1, 1);
//			for (Pair p : queries[i])
//			{
//				int r = p.v;
//				int ind = p.ind;
//				ans[ind] = tree.query(i+1, r+1);
//			}
			int ll = queries[i][0].length;
			for (int j = 0; j < ll; j++)
			{
				int r = queries[i][0][j];
				int ind = queries[i][1][j];
				ans[ind] = tree.query(i+1, r+1);
			}
		}
		
		for (int i = 0; i < q; i++)
			pw.println(ans[i]);
		
		pw.flush();
		pw.close();
	}
	
	private static void buildF()
	{
		TreeSet<Pair> s = new TreeSet<C.Pair>();
		int l = 0, r = 1;
		s.add(new Pair(cycle[0], 0));
		for (; l < n; l++)
		{
			while(r < n && r <= s.first().v)
			{
				s.add(new Pair(cycle[r], r));
				r++;
			}
			f[l] = r-1;
			s.remove(new Pair(cycle[l], l));
		}
	}
	
	static class Pair implements Comparable<Pair>
	{
		int v, ind;

		public Pair(int v, int ind)
		{
			this.v = v;
			this.ind = ind;
		}

		@Override
		public int compareTo(Pair p)
		{
			if(v != p.v)
				return v - p.v;
			return ind - p.ind;
		}
	}

	private static int dfs(int u, int p, int d)
	{
		vis[u] = vid;
		depth[u] = d;
		int min = d;
		for (int v : adj[u])
		{
			if(vis[v] != vid)
			{
				int mn = dfs(v, u, d+1);
				if(min > mn)
					min = mn;
				if(mn > d)
				{
					set[sInd++] = wrap(v, u);
				}
			}else
			{
				if(v != p)
					min = Math.min(min, depth[v]);
			}
		}
		return min;
	}

	static int mx;
	static void maxCycle(int u)
	{
		vis[u] = vid;
		mx = Math.max(mx, u);
		for (int v : adj[u])
		{
			if(vis[v] != vid && Arrays.binarySearch(set, wrap(u, v)) < 0)
			{
				maxCycle(v);
			}
		}
	}
	
	static long wrap(int a, int b)
	{
		return (1l*Math.min(a, b) << 31) + Math.max(a, b);
	}
	
	static class SegmentTree
	{
		int N; 			//the number of elements in the array as a power of 2 (i.e. after padding)
		int[] array;
		long[] sTree, lazy;
		
		SegmentTree(int[] in)		
		{
			array = in; N = in.length - 1;
			sTree = new long[N<<1];		//no. of nodes = 2*N - 1, we add one to cross out index zero
			lazy = new long[N<<1];
			build(1,1,N);
		}
		
		void build(int node, int b, int e)	// O(n)
		{
			if(b == e)					
				sTree[node] = array[b];	// modify base case
			else						
			{
				int mid = b + e >> 1;
				build(node<<1,b,mid);
				build(node<<1|1,mid+1,e);
				sTree[node] = sTree[node<<1]+sTree[node<<1|1];	// modify merging
			}
		}
		
		
		void update_point(int index, int val)			// O(log n)
		{
			index += N - 1;				
			sTree[index] += val;	// base case		
			while(index>1)				
			{
				index >>= 1;
				sTree[index] = sTree[index<<1] + sTree[index<<1|1];		// merging
			}
		}
		
		
		void update_range(int i, int j, int val)		// O(log n) 
		{
			update_range(1,1,N,i,j,val);
		}
		
		void update_range(int node, int b, int e, int i, int j, int val)
		{
			if(i > e || j < b)		
				return;
			if(b >= i && e <= j)		
			{
				sTree[node] += (e-b+1)*val;			// how value node carrying is modified
				lazy[node] += val;			// lazy value for node
			}							
			else		
			{
				int mid = b + e >> 1;
				propagate(node, b, mid, e);
				update_range(node<<1,b,mid,i,j,val);
				update_range(node<<1|1,mid+1,e,i,j,val);
				sTree[node] = sTree[node<<1] + sTree[node<<1|1];		// merging
			}
			
		}
		
		// modify
		void propagate(int node, int b, int mid, int e)		
		{
			lazy[node<<1] += lazy[node];
			lazy[node<<1|1] += lazy[node];
			sTree[node<<1] += (mid-b+1)*lazy[node];		
			sTree[node<<1|1] += (e-mid)*lazy[node];		
			lazy[node] = 0;
		}
		
		long query(int i, int j)
		{
			return query(1,1,N,i,j);
		}
		
		long query(int node, int b, int e, int i, int j)	// O(log n)
		{
			if(i>e || j <b)
				return 0;		// base case 1
			if(b>= i && e <= j)
				return sTree[node];	// base case 2
			int mid = b + e >> 1;
			propagate(node, b, mid, e);
			long q1 = query(node<<1,b,mid,i,j);
			long q2 = query(node<<1|1,mid+1,e,i,j);
			return q1 + q2;	// merging
					
		}
	}

	
	
	
	
	
	
	static class Scanner
	{
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s)
		{
			br = new BufferedReader(new InputStreamReader(s));
		}

		public Scanner(String s) throws FileNotFoundException
		{
			br = new BufferedReader(new FileReader(new File((s))));
		}

		public String next() throws IOException
		{
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException
		{
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException
		{
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException
		{
			return br.readLine();
		}

		public double nextDouble() throws IOException
		{
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-')
			{
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.')
				{
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else
				{
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public boolean ready() throws IOException
		{
			return br.ready();
		}
	}
}
