Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
A tree is free real estate: there is only one simple path between every pair, so it imposes no constraints. Every constraint comes from cycles.
Take a simple cycle and pick two vertices on it. The two arcs between them must have equal XOR. Since both arcs include and , this means the XOR of every other vertex on the cycle must be .
That condition is insanely strong. On any simple cycle, all vertices must have the same value. If the cycle length is odd, that common value must be .
An edge lies on some cycle exactly when it is not a bridge. So every non-bridge edge forces its endpoints to be equal.
After deleting bridges, each remaining connected component has one shared value. If that component is non-bipartite, it contains an odd cycle, so that shared value must be . Then just merge equal vertices with DSU, apply fixed values, and count free DSU components.
The whole problem is cycles. Trees do absolutely nothing here, because between two vertices there is only one simple path. No alternative path, no constraint, no drama.
Cycle Constraint
Consider a simple cycle , and pick two distinct vertices and on it. There are exactly two simple paths between them along the cycle: the two arcs.
Balanced means these two path XORs are equal.
Both arcs include and , so if we XOR the two path values together, and cancel out. What remains is exactly the XOR of all other vertices on the cycle. Therefore:
for every pair on the cycle.
Now pick three vertices on the cycle. Applying the condition to pairs and gives the same total cycle XOR on the left, so it forces
Since the choice was arbitrary, all vertices on a simple cycle must have the same value.
If the cycle length is even, that is enough. If the cycle length is odd and every vertex has value , then the XOR of all vertices except two is still , so we need .
So every simple cycle says:
Bridges Are The Split Point
An edge is on a cycle if and only if it is not a bridge.
Since every cycle forces all its vertices equal, every non-bridge edge forces its endpoints to be equal. So we can:
This creates components where all vertices must share one value.
Now, if one of these components contains an odd cycle, that shared value must be . A connected undirected graph contains an odd cycle exactly when it is not bipartite. So after ignoring bridges, we check each component for bipartiteness:
Vertices connected only by bridges stay independent unless fixed by input. That is why the tree sample has every unknown fully free.
Handling Fixed Values
Use a DSU with XOR potentials. It supports constraints of the form
We only need:
If a new constraint contradicts previous ones, the answer is .
After all constraints:
So if there are free DSU components, the answer is simply
No hidden bit DP nonsense. The graph does the hard part; counting is chill.
Complexity
Bridge-finding, bipartite checking, and DSU operations are all linear up to inverse-Ackermann factors:
This easily fits the limits.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
const ll MOD = 998244353;
ll modpow(ll a, int e) {
a %= MOD;
ll r = 1;
while (e) {
if (e & 1) r = r * a % MOD;
a = a * a % MOD;
e >>= 1;
}
return r;
}
struct XorDSU {
vector<int> p, sz;
vector<ll> xr; // value[x] xor value[parent[x]]
XorDSU(int n = 0) { init(n); }
void init(int n) {
p.resize(n);
sz.assign(n, 1);
xr.assign(n, 0);
iota(p.begin(), p.end(), 0);
}
pair<int, ll> find(int x) {
if (p[x] == x) return {x, 0};
auto [r, v] = find(p[x]);
xr[x] ^= v;
p[x] = r;
return {p[x], xr[x]};
}
bool unite(int a, int b, ll w) { // value[a] xor value[b] = w
auto [ra, xa] = find(a);
auto [rb, xb] = find(b);
if (ra == rb) return ((xa ^ xb) == w);
if (sz[ra] < sz[rb]) {
swap(ra, rb);
swap(xa, xb);
}
p[rb] = ra;
xr[rb] = xa ^ xb ^ w;
sz[ra] += sz[rb];
return true;
}
};
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n, m;
ll V;
cin >> n >> m >> V;
vector<ll> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
vector<pair<int, int>> edges(m);
vector<vector<pair<int, int>>> g(n + 1);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
edges[i] = {u, v};
g[u].push_back({v, i});
g[v].push_back({u, i});
}
vector<int> tin(n + 1, 0), low(n + 1, 0), par(n + 1, -1), pe(n + 1, -1), it(n + 1, 0);
vector<char> bridge(m, false);
int timer = 0;
for (int root = 1; root <= n; root++) {
if (tin[root]) continue;
vector<int> st;
st.push_back(root);
tin[root] = low[root] = ++timer;
while (!st.empty()) {
int u = st.back();
if (it[u] == (int)g[u].size()) {
st.pop_back();
if (par[u] != -1) {
int p = par[u];
low[p] = min(low[p], low[u]);
if (low[u] > tin[p]) bridge[pe[u]] = true;
}
continue;
}
auto [v, id] = g[u][it[u]++];
if (id == pe[u]) continue;
if (!tin[v]) {
par[v] = u;
pe[v] = id;
tin[v] = low[v] = ++timer;
st.push_back(v);
} else {
low[u] = min(low[u], tin[v]);
}
}
}
XorDSU dsu(n + 1); // node 0 is fixed zero
bool ok = true;
for (int i = 0; i < m; i++) {
if (!bridge[i]) {
auto [u, v] = edges[i];
ok &= dsu.unite(u, v, 0);
}
}
vector<int> color(n + 1, -1);
for (int s = 1; s <= n; s++) {
if (color[s] != -1) continue;
queue<int> q;
vector<int> verts;
bool bip = true;
color[s] = 0;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
verts.push_back(u);
for (auto [v, id] : g[u]) {
if (bridge[id]) continue;
if (color[v] == -1) {
color[v] = color[u] ^ 1;
q.push(v);
} else if (color[v] == color[u]) {
bip = false;
}
}
}
if (!bip) ok &= dsu.unite(0, s, 0);
}
for (int i = 1; i <= n; i++) {
if (a[i] != -1) ok &= dsu.unite(0, i, a[i]);
}
if (!ok) {
cout << 0 << '\n';
continue;
}
int root0 = dsu.find(0).first;
unordered_set<int> free_roots;
free_roots.reserve(n * 2 + 1);
for (int i = 1; i <= n; i++) {
int r = dsu.find(i).first;
if (r != root0) free_roots.insert(r);
}
cout << modpow(V, (int)free_roots.size()) << '\n';
}
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
const ll MOD = 998244353;
ll modpow(ll a, int e) {
a %= MOD;
ll r = 1;
while (e) {
if (e & 1) r = r * a % MOD;
a = a * a % MOD;
e >>= 1;
}
return r;
}
struct XorDSU {
vector<int> p, sz;
vector<ll> xr; // value[x] xor value[parent[x]]
XorDSU(int n = 0) { init(n); }
void init(int n) {
p.resize(n);
sz.assign(n, 1);
xr.assign(n, 0);
iota(p.begin(), p.end(), 0);
}
pair<int, ll> find(int x) {
if (p[x] == x) return {x, 0};
auto [r, v] = find(p[x]);
xr[x] ^= v;
p[x] = r;
return {p[x], xr[x]};
}
bool unite(int a, int b, ll w) { // value[a] xor value[b] = w
auto [ra, xa] = find(a);
auto [rb, xb] = find(b);
if (ra == rb) return ((xa ^ xb) == w);
if (sz[ra] < sz[rb]) {
swap(ra, rb);
swap(xa, xb);
}
p[rb] = ra;
xr[rb] = xa ^ xb ^ w;
sz[ra] += sz[rb];
return true;
}
};
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n, m;
ll V;
cin >> n >> m >> V;
vector<ll> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
vector<pair<int, int>> edges(m);
vector<vector<pair<int, int>>> g(n + 1);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
edges[i] = {u, v};
g[u].push_back({v, i});
g[v].push_back({u, i});
}
vector<int> tin(n + 1, 0), low(n + 1, 0), par(n + 1, -1), pe(n + 1, -1), it(n + 1, 0);
vector<char> bridge(m, false);
int timer = 0;
for (int root = 1; root <= n; root++) {
if (tin[root]) continue;
vector<int> st;
st.push_back(root);
tin[root] = low[root] = ++timer;
while (!st.empty()) {
int u = st.back();
if (it[u] == (int)g[u].size()) {
st.pop_back();
if (par[u] != -1) {
int p = par[u];
low[p] = min(low[p], low[u]);
if (low[u] > tin[p]) bridge[pe[u]] = true;
}
continue;
}
auto [v, id] = g[u][it[u]++];
if (id == pe[u]) continue;
if (!tin[v]) {
par[v] = u;
pe[v] = id;
tin[v] = low[v] = ++timer;
st.push_back(v);
} else {
low[u] = min(low[u], tin[v]);
}
}
}
XorDSU dsu(n + 1); // node 0 is fixed zero
bool ok = true;
for (int i = 0; i < m; i++) {
if (!bridge[i]) {
auto [u, v] = edges[i];
ok &= dsu.unite(u, v, 0);
}
}
vector<int> color(n + 1, -1);
for (int s = 1; s <= n; s++) {
if (color[s] != -1) continue;
queue<int> q;
vector<int> verts;
bool bip = true;
color[s] = 0;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
verts.push_back(u);
for (auto [v, id] : g[u]) {
if (bridge[id]) continue;
if (color[v] == -1) {
color[v] = color[u] ^ 1;
q.push(v);
} else if (color[v] == color[u]) {
bip = false;
}
}
}
if (!bip) ok &= dsu.unite(0, s, 0);
}
for (int i = 1; i <= n; i++) {
if (a[i] != -1) ok &= dsu.unite(0, i, a[i]);
}
if (!ok) {
cout << 0 << '\n';
continue;
}
int root0 = dsu.find(0).first;
unordered_set<int> free_roots;
free_roots.reserve(n * 2 + 1);
for (int i = 1; i <= n; i++) {
int r = dsu.find(i).first;
if (r != root0) free_roots.insert(r);
}
cout << modpow(V, (int)free_roots.size()) << '\n';
}
}