P11644 [MX-X8-T3] "TAOI-3" Didi Loves Check-ins.

Original problem link: . --- One year ago, I failed miserably at NOIP 2023. One year later, I stood up again from where I fell. THUWC 2025 D1T1, I forcefully scored 76 points. ... Segment-tree-optimized DP is just too hard.

Student T is very indifferent about running. To make running even more boring, he decided to make an app called "Didi Loves Check-ins", so that users cannot check in for running anywhere. After finishing development, Student T plans to do a trial run, and he asked Student Y to help. In this check-in trial, there are $n$ nodes numbered $1 \sim n$, and $m$ undirected roads connecting two nodes. **It is guaranteed that the graph has no multiple edges and no self-loops.** Student Y needs to run from $s$ to $t$. Initially, Student Y's energy value is $0$. Each time Student Y runs along a road, Student T will treat him to a meal, increasing his energy value by $1$. During the trial, his **energy value cannot be negative.** Student Y also has a happiness value, initially $0$. When staying at some node, Student Y may choose to bitwise XOR his happiness value with his energy value, and then clear his energy value (i.e. set energy to $0$), or do nothing. Now Student Y wants to know whether he can **finally stay at** node $t$, use up all his energy (i.e. energy becomes $0$), and at that moment his happiness value is exactly $x$? **Note: after Student Y reaches node $\bm t$, he may choose not to stop and continue moving.** Because Student Y loves running, you need to answer $q$ queries. Each query gives $s, t, x$, and you need to tell Student Y whether he can meet his requirement.

The first line contains three non-negative integers $n, m, q$. The next $m$ lines each contain two positive integers $u, v$, representing a road connecting node $u$ and node $v$. The next $q$ lines each contain three non-negative integers $s, t, x$, representing a query.

Output $q$ lines. For each query, if Student Y can meet his requirement, output `tribool`; otherwise output `expand`.

**[Sample Explanation #1]**  As shown in the figure, for the first query, Student Y starts from node $1$, goes along one road and arrives at node $2$. At this time his energy value is $1$. He then performs one operation: his energy value becomes $0$, and his happiness value becomes $1$, which satisfies the requirement. For the second query, it can be shown that there is no valid plan. **[Constraints]** **This problem uses bundled testdata.** - Subtask 1 (22 points): $\max(n, m, q, x) \leq 50$. - Subtask 2 (22 points): $m = n - 1$ and the graph is connected. - Subtask 3 (24 points): $x \leq 1$. - Subtask 4 (32 points): no special constraints. For all testdata, it is guaranteed that $2 \leq n \leq 2\times 10^5$, $0 \leq m \leq 3\times 10^5$, $1 \leq q \leq 2\times 10^5$, $1 \leq s, t, u, v \leq n$, $0 \leq x \leq 10^9$, and the given undirected graph has no multiple edges and no self-loops. Translated by ChatGPT 5