Shortest Path - Taukir Khatri

// ====================================
// CODE BY Taukir Khatri
// ====================================

#include "bits/stdc++.h"
// #include "ext/pb_ds/assoc_container.hpp"
// #include "ext/pb_ds/tree_policy.hpp"
using namespace std;
// using namespace __gnu_pbds;

#define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

typedef long long  ll;
#define vi         vector<ll>
#define vb         vector<bool>
#define vvi        vector<vector<ll>>
#define pi         pair<ll,ll>
#define vpi        vector<pi>
#define mii        map<ll,ll>
#define qi         queue<ll>
#define si         stack<ll>
#define pqd        priority_queue<ll>
#define pqa        priority_queue<ll, vi, greater<ll>()>
#define ff         first
#define ss         second
#define pb         push_back
#define ins        insert
#define pob        pop_back
#define puf        push_front
#define pof        pop_front
#define sz         size
#define mp         make_pair
#define all(x)     x.begin(), x.end()
#define bs(a,x)    binary_search(all(a), x)
#define lb(a,x)    lower_bound(all(a), x)
#define lbi(a,x)   lb(a,x) - a.begin()
#define ub(a,x)    upper_bound(all(a), x)
#define ubi(a,x)   ub(a,x) - a.begin()

#define sortasc(x) sort(all(x))
#define sortdes(x) sort(all(x), greater<ll>())

#define setbits(x)       __builtin_popcountll(x)
#define zrobits(x)       __builtin_ctzll(x)
#define leadingzrs(x)    __builtin_clzll(x)
#define trailingzrs(x)   __builtin_ctzll(x)
#define parity(x)        __builtin_parityll(x)

const ll M = 1e9+7;

ll mos() { return 0LL; }
template<typename T, typename... Args>
T mos(T a, Args... args) { return ((a + mos(args...))%M + M)%M; }

long long mop() { return 1LL; }
template<typename T, typename... Args>
T mop(T a, Args... args) { return (a*mop(args...))%M; }

#define pow2(x)    (1ll<<(x))
#define PINF       LLONG_MAX
#define NINF       LLONG_MIN

// template<typename T = ll>
// using oset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define nl         "\n"
#define print(a)   for (auto &i : a) cout << i << " "; cout << nl
#define yesno(x)   cout << (((x)) ? "YES" : "NO") << nl
#define cntdig(x)  floor(log(x) + 1)

#define fra(i,init,n,inc) for(i=(init);i<(n);i+=(inc))
#define frd(i,init,n,dec) for(i=(init);i>=(n);i-=(dec))

#define ts to_string
string ts(char c) { return string(1, c); }
string ts(bool b) { return b ? "true" : "false"; }
string ts(const char* s) { return (string)s; }
string ts(string s) { return s; }
template<class A> string ts(complex<A> c) { stringstream ss; ss << c; return ss.str(); }
string ts(vector<bool> v) { string res = "{"; for(int i = 0; i < v.sz(); ++i) res += char('0' + v[i]); res += "}"; return res; }
template<size_t SZ> string ts(bitset<SZ> b) { string res = ""; for(int i = 0; i < SZ; ++i) res += char('0' + b[i]); return res; }
template<class A, class B> string ts(pair<A,B> p);
template<class T> string ts(T v) { bool fst = 1; string res = "{"; for (const auto& x: v) { if (!fst) res += ", "; fst = 0; res += ts(x); } res += "}"; return res; }
template<class A, class B> string ts(pair<A,B> p) { return "(" + ts(p.f) + ", " + ts(p.s) + ")"; }

void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) { cerr << ts(h); if (sizeof...(t)) cerr << ", "; DBG(t...); }
void EDBG(string names) { names = names; }
template<class H, class... T> void EDBG(string names, H h, T... t) { auto pos = names.find(','); auto first_name = names.substr(0, pos); auto rest = names.substr(pos + 1); while(rest.front() == ' ') { rest = rest.substr(1); } cerr << "[" << first_name << "] : [" << ts(h) << "]" << nl; EDBG(rest, t...); }

#ifdef LOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "] : [", DBG(__VA_ARGS__)
#define edbg(...) EDBG(#__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(...) 0
#define edbg(...) 0
#endif

template<typename T = ll>
void tv(vector<T> &a, ll n) { ll i = 0; fra(i,0,n,1) { T t; cin >> t; a.pb(t); } }

void my_sol() {
    ll n, m, k, i = 0, j = 0, cnt = 0, sum = 0, maxi = NINF, mini = PINF;
    string s,s1,s2;
    cin >> n >> m >> k;
    vi g[n+1];
    fra(i,0,m,1) {
        ll u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    set<tuple<ll,ll,ll>> blocked;
    fra(i,0,k,1) {
        ll a, b, c;
        cin >> a >> b >> c;
        blocked.insert({a,b,c});
    }
    vector<bool> vis(n+1);
    vi d(n+1), p(n+1, -1);
    queue<ll> q;
    q.push(1);
    vis[1] = true;
    d[1] = 0;
    p[1] = -1;
    while(!q.empty()) {
        ll u = q.front();
        q.pop();
        for(auto v:g[u]) {
            dbg(u, v, vis);
            if(!vis[v]) {
                d[v]=d[u]+1;
                p[v]=u;
                vis[v] = true;
                vi cur;
                ll cn = v;
                while(cur.sz() < 3 && cn!=-1) {
                    cur.pb(cn);
                    cn = p[cn];
                }
                dbg(cur);
                if(cur.sz()==3) {
                    tuple<ll,ll,ll> check = {cur[2], cur[1], cur[0]};
                    if(blocked.count(check)) {
                        dbg("NOT VISITING", u, v);
                        d[v]=0;
                        p[v]=-1;
                        vis[v] = false;
                        continue;
                    }
                }
                q.push(v);
            }
        }
    }

    if(!vis[n]) {
        cout << -1 << nl;
        return;
    }

    vi ans;
    for(ll i=n;i!=-1;i=p[i]) ans.pb(i);

    reverse(all(ans));
    cout << d[n] << nl;
    print(ans);
}

int main() {
    fast_io;
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
        auto start = std::chrono::high_resolution_clock::now();
    #endif

    ll t = 1;
    while(t--)
        my_sol();

    #ifndef ONLINE_JUDGE
        auto stop = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(stop - start);
        long double t1 = (long double)duration.count()/1000000;
        cout << "\n\nTime taken "<< fixed << setprecision(6) << t1 << " seconds" << "\n";
    #endif
    return 0;
}