题解

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3005, M = 40005;
int n, m, k, d = 1, a[N], b[M], c[M], f[M * 2], g[M * 2], o[M], p;
bool h[M * 2];
unordered_set<ll> e;

int main() {
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> n >> m >> k;
for (int i = 0; i < m; ++i) {
int u, v; cin >> u >> v;
b[++d] = v; c[d] = a[u]; a[u] = d;
b[++d] = u; c[d] = a[v]; a[v] = d;
}
for (int i = 0; i < k; ++i) {
int x, y, z; cin >> x >> y >> z;
e.insert((1LL * x * N + y) * N + z);
}
int l = 0, r = 0;
for (int i = a[1]; i; i = c[i]) {
int v = b[i];
if (!e.count((1LL * 0 * N + 1) * N + v)) {
h[i] = 1;
f[++r] = i;
}
}
int t = 0;
while (l < r) {
int u = f[++l];
int x = b[u ^ 1], y = b[u];
if (y == n) { t = u; break; }
for (int i = a[y]; i; i = c[i]) {
int z = b[i];
if (e.count((1LL * x * N + y) * N + z)) continue;
if (!h[i]) {
h[i] = 1;
g[i] = u;
f[++r] = i;
}
}
}
if (!t) { cout << -1 << '\n'; return 0; }
for (int i = t; i; i = g[i]) o[++p] = b[i];
o[++p] = 1;
cout << p - 1 << '\n';
for (int i = p; i >= 1; --i) cout << o[i] << " \n"[i == 1];
return 0;
}