Background

Original problem link: https://oier.team/problems/X8D.

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.

Problem Description

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.

Input Format

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 Format

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

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

tribool
expand
tribool
expand

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

tribool
expand
tribool
expand

Hint

[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