text: from random import *
  
  ''' Generate a random array of integers with elements in the range [L, R] '''
  def genRandomArray(N, L, R):
  	a = [randrange(L,R+1) for _ in xrange(N)]
  	return a
  
  ''' Generate a random string from characters in the range [A, B]'''
  def genRandomString(N, A, B):
  	l = genRandomArray(N, ord(A), ord(B))
  	s = ''
  	for char in l: s += chr(char)
  	return s
  
  ''' Generate a random permutation of [1, 2 ... N] '''
  def genRandomPermutation(N):
  	permutation = range(1, N+1)
  	shuffle(permutation)
  	return permutation
  
  ''' Generate a random unweighted tree'''
  def genRandomTree(N):
  	edges = []	
  	for u in xrange(2,N+1):
  		v = randrange(1,u)
  		edges.append([u,v])
  		
  	permutation = genRandomPermutation(N)
  	
  	for i in xrange(0,N-1):
  		u, v = edges[i]
  		u = permutation[u-1]
  		v = permutation[v-1]
  		edges[i] = (u,v)
  	return edges
  
  ''' Generate a random weighted tree '''
  def genRandomWeightedTree(N, L, R):
  	weigths = genRandomArray(N-1, L, R)
  	tree = genRandomTree(N)
  	wtree = []
  	
  	for i in xrange(0,N-1):
  		u, v, w = tree[i][0], tree[i][1], weigths[i]
  		wtree.append((u, v, w))
  	
  	return wtree
  
  ''' Undirected, no multiedges and no self-loops '''
  def genRandomGraph(N, E):
  	edges = {}
  	
  	if N == 1: return []
  	
  	for i in xrange(E):
  		u = randrange(1,N+1)
  		v = u
  		while v == u: v = randrange(1,N+1)
  		
  		while (u,v) in edges or (v,u) in edges:
  			u = randrange(1,N+1)
  			v = u
  			while v == u: v = randrange(1,N+1)
  		
  		edges[(u,v)] = 1
  	
  	ret = []
  	for edge in edges: ret.append(edge)
  	
  	return ret
  
  ''' Undirected, no multiedges, no self-loops, connected '''
  def genRandomConnectedGraph(N, E):
  	E -= N-1
  	tree = genRandomTree(N)
  	edges = {}
  	for edge in tree:
  		edges[edge] = 1
  	
  	for i in xrange(E):
  		u = randrange(1,N+1)
  		v = u
  		while v == u: v = randrange(1,N+1)
  		
  		while (u,v) in edges or (v,u) in edges:
  			u = randrange(1,N+1)
  			v = u
  			while v == u: v = randrange(1,N+1)
  		
  		edges[(u,v)] = 1
  	
  	ret = []
  	for edge in edges: ret.append(edge)
  	
  	return ret
  
  ''' Undirected, no multiedges, no self-loops, can be forced to be connected '''
  def genRandomWeightedGraph(N, E, L, R, connected = False):
  	graph = []
  	if not connected:
  		graph = genRandomGraph(N, E)
  	else:
  		graph = genRandomConnectedGraph(N, E)
  	
  	weights = genRandomArray(E, L, R)
  	
  	wgraph = []
  	for i in xrange(E):
  		u, v, w = graph[i][0], graph[i][1], weights[i]
  		wgraph.append((u,v,w))
  	return wgraph
  
  '''
  Available Functions
  
  genRandomArray(size, low, high)
  To robustly test on arrays, generate arrays with all zeroes, all same numbers etc manually
  
  genRandomString(size, lowchar, highchar)
  To robustly test on strings, manually generate strings made up of the same character
  
  genRandomPermutation(size)
  
  genRandomTree(size)
  genRandomWeightedTree(size, low, high)
  genRandomGraph(nodes, edges)
  genRandomConnectedGraph(nodes, edges)
  genRandomWeightedGraph(nodes, edges, low, high)
  
  To robustly test on graphs, manually generate star graphs, linear chain graph, complete graph etc
  
  Generate Test Case Below!
  '''
  
  if __name__ == "__main__":
  	T = 10
  	print T
  	for _ in xrange(T):
  		N = 100000
  		M = 4
  
  		array = genRandomArray(N, 1, 1001)
  			
  		x = randrange(1, N)
  		y = randrange(x, N+1)
  		
  		print N, M, x, y
  		for i in array:
  			print i,
  		print
  
  '''
  
  End of main!
  
  '''
  