struct weightedDSU {
	vector<int> parent, weight, index;
 
	weightedDSU(int n) : parent(n), weight(n, INF), index(n) {
		for (int i = 0; i < n; i++) {
			parent[i] = i;
			index[i] = rand();
		}
	}
 
	int getRoot(int v, int w = INF - 1) {
		while (weight[v] <= w) {
			while (weight[parent[v]] <= weight[v])
				parent[v] = parent[parent[v]];
			v = parent[v];
		}
		return v;
	}
 
	void addEdgeHelper(int u, int v, int w) {
		while (u != v) {
			u = getRoot(u, w);
			v = getRoot(v, w);
			if (index[u] < index[v])
				swap(u, v);
			int temp_weight = weight[v], temp_parent = parent[v];
			parent[v] = u;
			weight[v] = w;
			u = temp_parent;
			w = temp_weight;
		}
	}

	int mainEdge(int u, int v) {
		if (getRoot(u) != getRoot(v))
			return -1;
		while (parent[u] != v && parent[v] != u) {
			if (weight[u] < weight[v])
				u = parent[u];
			else
				v = parent[v];
		}
		if (parent[u] == v)
			return u;
		else
			return v;
	}
 
	void addEdge(int u, int v, int w) {
		if (u == v)
			return;
		int p = mainEdge(u, v);
		if (p == -1)
			addEdgeHelper(u, v, w);
		else if (weight[p] > w) {
			parent[p] = p;
			weight[p] = INF;
			addEdgeHelper(u, v, w);
		}
	}
};

struct weightedDSU {
	vector<int> parent, index, size, weight;
 
	weightedDSU(int n) : parent(n), weight(n, INF), index(n), size(n, 1) {
		for (int i = 0; i < n; i++) {
			parent[i] = i;
			index[i] = rand();
		}
	}
 
	int getRoot(int v, int w = INF - 1) {
		while (weight[v] <= w) {
			while (weight[parent[v]] <= weight[v]){
				size[parent[v]] -= size[v];
				parent[v] = parent[parent[v]];
			}
			v = parent[v];
		}
		return v;
	}
    
	void disconnect(int v){
		if(parent[v] == v)
			return;
		disconnect(parent[v]);
		size[parent[v]] -= size[v];
	}
    
	int connect(int v, int w = INF - 1){
		while(weight[v] <= w){
			size[parent[v]] += size[v];
			v = parent[v];
		}
		return v;
	}
    
	void addEdgeHelper(int u, int v, int w) {
		disconnect(u);
		disconnect(v);
		while (u != v) {
			u = connect(u, w);
			v = connect(v, w);
			if (index[u] < index[v])
				swap(u, v);
			int temp_weight = weight[v], temp_parent = parent[v];
			parent[v] = u;
			weight[v] = w;
			u = temp_parent;
			w = temp_weight;
		}
		connect(v);
	}
    
	int mainEdge(int u, int v) {
		if (getRoot(u) != getRoot(v))
			return -1;
		while (parent[u] != v && parent[v] != u) {
			if (weight[u] < weight[v])
				u = parent[u];
			else
				v = parent[v];
		}
		if (parent[u] == v)
			return u;
		else
			return v;
	}
    
	void addEdge(int u, int v, int w) {
		if (u == v)
			return;
		int p = mainEdge(u, v);
		if (p == -1)
			addEdgeHelper(u, v, w);
		else if (weight[p] > w) {
			int p1 = p;
			while(parent[p1] != p1){
				p1 = parent[p1];
				size[p1] -= size[p];
			}
			parent[p] = p;
			weight[p] = INF;
			addEdgeHelper(u, v, w);
		}
	}
};

We maintain a maximum spanning forest where the edges are ordered by their deletion time. When we get to deleting an edge, if it is not in the msf we know the component will stay connected, otherwise we delete it as described earlier. this solution has complexity of $$$O(n + (m + k) \log n)$$$.
code

The straight forward approach will be to maintain a maximum spanning forest where the edges have weights of their insertion time and use the treap approach described earlier. But because are queries are on subarrays with increasing left side, when going to the next day we can simply delete all the edges from the discarded day from smallest to largest. This solution has time complexity of $$$O(n + q \log n)$$$.
submission

First we will turn the queries into queries asking about only using a subarray of edges by concatenating the array to the end of it. At each index i we want to know last[i] which is the minimum left index j such that using all the edges between i and j results in a bipartite graph. When answering queries if the subarray asked on $$$[l, r]$$$ holds true that l < last[r] than there is an odd cycle. To calculate last[i] we go from left to right and maintain a maximum spanning forest where the edge weights are their indices. Because we save only bipartite graphs in our DS if we can maintain the evenness of a path between u and v we will be able to check if they are of the same color. we do this by maintaining an additional value on each edge and that is if it represents an even path between the 2 nodes or an odd path (exact implementation can be seen in the code I have written). Using this when we are adding an edge to the msf we can check if it creates an odd cycle. We remove edges from smallest to largest until the resulting edge insertion does not result in an odd cycle and therefore the graph is bipartite. This solution has time complexity of $$$O(n + m \log n + q)$$$.
submission

we will add the edges in order of $$$g_i$$$ where their edge weights are $$$s_i$$$ and maintain a minimum spanning forest. When using all edges up to (and including) edge i (after sorting) if the graph is connected we have a solution with $$$a = g_i$$$ and b equals the maximum edge weight in our msf. we will do the minimum on each edge prefix and get our answer. This solution has time complexity of $$$O(n + m \log n)$$$. submission

First we will notice that a graph has a subgraph that is sunny if and only if each connected component has even size. If a connected component has an odd size we get a contradiction because the sum of the degrees should be even but is odd. With a connected component of even size we can use the following greedy algorithm to get a sunny subgraph: create a spanning rooted tree of the connected component, we connect an edge from v to a child of him u if the size of the subtree is odd. Using this idea we can add the edges in order and maintain a minimum spanning tree. We delete the maximal edge while when deleting it the statement will still hold true. the maximum edge weight in the msf is our answer. This solution has time complexity of $$$O(n + m \log n)$$$.
submission