Sabotage Running Check-In

In this problem, you are given an undirected simple graph with n nodes and m edges (there are no self‐loops and no multiple edges). There are q queries; in each query you are given three integers s, t, and x. A runner starts at node s with energy 0 and happiness 0. Every time he runs along an edge, his energy increases by 1 (because at each edge his friend treats him to a meal). During the run his energy is never allowed to become negative. At any node, he may choose to perform a "check‐in" operation: his current energy value e is bitwise XORed into his happiness (i.e. happiness = happiness \oplus e) and his energy resets to 0. The runner may perform the check‑in operation arbitrarily many times (or not at all) at any node (even when his energy is 0). Note that after reaching node t (the target) he is allowed to continue moving, but eventually he must stop at node t with his energy at 0 and his happiness exactly equal to x.

Your task is to determine for each query whether it is possible to design a route starting from s and eventually stopping at t (with energy 0) such that the final happiness is exactly x.

Important observations:

1. Whenever the runner runs an edge, his energy increases by 1. Thus, if he runs a segment of L edges (possibly with cycles or detours), then before a check‑in his energy will be L and he will deposit the number L into his happiness when doing the check‑in.
2. You may split the entire journey into several segments. Suppose the segments have lengths L₁, L₂, ..., L_k; then the final happiness will be L₁ \oplus L₂ \oplus ... \oplus L_k.
3. The possibility of choosing an arbitrary value for a segment depends on the structure of the graph:
   • If the connected component containing s and t is non-bipartite (i.e. it contains an odd cycle), then for any two vertices in that component one may design a walk whose length is arbitrarily large. In this case any integer value can be achieved for a segment.
   • If the component is bipartite, then the parity of the length of any walk between two vertices is fixed. In particular, if we assign a 0/1 color to the bipartite sets then any walk from s to t will have length parity equal to color[s] ⊕ color[t]. Consequently, if the component is bipartite then in every valid route the XOR of deposited segment lengths will always have the same least significant bit as color[s] ⊕ color[t].

Thus, the answer for each query is determined as follows:

• If s and t are not in the same connected component, output No.
• If they are in the same component and that component is non-bipartite, output Yes (any value of x is achievable).
• If the component is bipartite, then let p = 0 if s and t are in the same part and p = 1 otherwise. In this case, a necessary condition is that x has the same parity as p (i.e. x mod 2 == p); output Yes if this holds, and No otherwise.

Your task is to answer all q queries.

Note: All formulas must be written in LaTeX format. For example, the XOR of the lengths is written as \(L_1 \oplus L_2 \oplus \cdots \oplus L_k\), and the condition on parity may be written as \(x \bmod 2 = p\).

inputFormat

The input begins with two integers \(n\) and \(m\) representing the number of nodes and edges respectively \((1 \le n, m \le 10^5)\). Each of the next \(m\) lines contains two integers \(u\) and \(v\) indicating an undirected edge between nodes \(u\) and \(v\) \((1 \le u, v \le n)\).

The next line contains an integer \(q\) \((1 \le q \le 10^5)\), the number of queries. Each of the following \(q\) lines contains three integers \(s\), \(t\), and \(x\) \((1 \le s, t \le n,\; 0 \le x \le 10^9)\) representing a query.

outputFormat

For each query, output a single line containing either Yes or No indicating whether it is possible to design a route in which the runner eventually stops at node \(t\) with energy \(0\) and happiness exactly \(x\).

sample

3 2
1 2
2 3
2
1 3 2
1 3 3

Yes
No