It's easy. My solution gets AC because checker (or interactor) is incorrect.

The official editorial is ready! https://csacademy.com/contest/round-64/analysis/

It seems they don't care about correctness.

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstring>
#include <cmath>
#include <complex>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define mp make_pair

const int N = 1 << 14;
const int NN = N + 5;
const int LOG = 15;
vector<int> g[NN];
int n, m, q;
int par[NN][LOG];
set<int> edgesUp[NN];
int t[NN][2];
int T;
int jmp[NN];
int h[N];

struct Node {
    int l, r;
    pii val;
    
    Node() : l(), r(), val() {}
    Node(int _l, int _r) : l(_l), r(_r), val(mp(N, _l)) {}
};
Node tree[2 * N + 5];

void buildTree() {
    for (int i = 0; i < N; i++)
        tree[N + i] = Node(i, i + 1);
    for (int i = N - 1; i > 0; i--)
        tree[i] = Node(tree[2 * i].l, tree[2 * i + 1].r);
}

void setVal(int v, pii x) {
    v += N;
    tree[v].val = x;
    while(v > 1) {
        v >>= 1;
        tree[v].val = min(tree[2 * v].val, tree[2 * v + 1].val);
    }
}

pii getMin(int v, int l, int r) {
    if (l <= tree[v].l && tree[v].r <= r)
        return tree[v].val;
    if (l >= tree[v].r || tree[v].l >= r)
        return mp(N, -1);
    return min(getMin(2 * v, l, r), getMin(2 * v + 1, l, r));
}

void dfs(int v) {
    edgesUp[v].insert(h[v]);
    t[v][0] = T++;
    for (int u : g[v]) {
        if (h[u] != -1) {
            if (h[u] < h[v] - 1)
                edgesUp[v].insert(h[u]);
            continue;
        }
        h[u] = h[v] + 1;
        par[u][0] = v;
        for (int k = 0; k < LOG - 1; k++) {
            int w = par[u][k];
            if (w != -1)
                par[u][k + 1] = par[w][k];
        }
        dfs(u);
    }
    t[v][1] = T;
}

int up(int v, int dh) {
    for (int k = LOG - 1; k >= 0; k--) {
        if (dh < (1 << k)) continue;
        dh -= 1 << k;
        v = par[v][k];
    }
    return v;
}
int LCA(int v, int u) {
    if (h[v] > h[u]) swap(v, u);
    u = up(u, h[u] - h[v]);
    if (v == u) return v;
    for (int k = LOG - 1; k >= 0; k--) {
        if (par[v][k] != par[u][k]) {
            v = par[v][k];
            u = par[u][k];
        }
    }
    return par[v][0];
}

int jump(int v) {
    return jmp[v] == v ? v : jmp[v] = jump(jmp[v]);
}

void precalc() {
    for (int v = 0; v < n; v++) {
        jmp[v] = v;
        h[v] = -1;
        for (int k = 0; k < LOG; k++)
            par[v][k] = -1;
    }
    h[0] = 0;
    dfs(0);
    buildTree();
    for (int v = 0; v < n; v++)
        setVal(t[v][0], mp(*edgesUp[v].begin(), v));
}

void query(int v, int u) {
    int w = LCA(v, u);
    
    while(h[v] > h[w]) {
        if (v != jmp[v]) {
            v = jump(v);
            continue;
        }
        pii s = getMin(1, t[v][0], t[v][1]);
        if (s.first >= h[v]) {
            jmp[v] = par[v][0];
            continue;
        }
        v = s.second;
        u = up(v, h[v] - s.first);
        printf("0 %d %d\n", v + 1, u + 1);
        fflush(stdout);
        edgesUp[v].erase(edgesUp[v].begin());
        setVal(t[v][0], mp(*edgesUp[v].begin(), v));
        return;
    }
    swap(v, u);
    while(h[v] > h[w]) {
        if (v != jmp[v]) {
            v = jump(v);
            continue;
        }
        pii s = getMin(1, t[v][0], t[v][1]);
        if (s.first >= h[v]) {
            jmp[v] = par[v][0];
            continue;
        }
        v = s.second;
        u = up(v, h[v] - s.first);
        printf("0 %d %d\n", v + 1, u + 1);
        fflush(stdout);
        edgesUp[v].erase(edgesUp[v].begin());
        setVal(t[v][0], mp(*edgesUp[v].begin(), v));
        return;
    }
    printf("1\n");
    fflush(stdout);
}

int main() {
    
    scanf("%d%d%d", &n, &m, &q);
    while(m--) {
        int v, u;
        scanf("%d%d", &v, &u);
        v--;u--;
        g[v].push_back(u);
        g[u].push_back(v);
    }
    precalc();
    while(q--) {
        int v, u;
        scanf("%d%d", &v, &u);
        v--;u--;
        query(v, u);
    }
    
    return 0;
}

Here is what you should do!

Fix any spanning tree T. We'll never delete the edges from T. A T-edge is an edge in T, a T-path is a path in T. Make a few observations:

• The path from u to v is unique iff the T-path from u to v consist of bridges only.
• If a non-tree edges u - v is present it prevents the edges on the T-path from u to v in T from being bridges. Let's say that this edges 'covers' the edges in that path.
• An edge is a bridge iff it it not covered. A path consists of bridges iff none of it's edges are covered. Any edge covering an edge of a path is a valid output when that path is queried.

We'll use heavy-light decomposition.

• Maintain the number of edges covering a T-edge and query the sum on the T-path from u to v to get whether any edge on that path is covered. (Operations: path sum, path add)
• We can then find any covered edge on the path (Operations: path sum, walk the segtree down to find a non-zero segtree-leaf) (Can be replaced by walking up the tree and something like path-compression from union-find.)
• To Find any edge that covers a given edge e maintain an unordered set in each segtree node that stores the edges that did a range-add update to that node. Treat these sets like lazy updates that do not propagate. If we walk from the segtree-node of e to the segtree-root, we'll encounter all edges covering e in exactly in of the sets, so we can just find a non-empty set and pick an edge to delete from the sets, range add  - 1 and print for the query.

The total runtime is .

A simpler solution can pass for some reason (My solution with lowest memory usage uses #pragma, but it pases without it). (You might need to submit it a few times, as you can get "Something bad happened. Please resubmit and contact us.")

To check whether any edge on the T-path from a to b is covered, iterate over all edges u - v and check whether the T-paths from a to b and from u to v share an edge. (If yes, then u - v covers that edge and can be output.) This can be done with a bunch of (but constant number of) LCA queries.

You should stop after 500 prints I guess?

As it is stated that your program must be terminated after the piles become 0 or there are already 500 interactions occured.

I am surprised that no one asked if it is 500 "turns" or 500 "moves from both players" in the real time contest.