HackerRank DAG Queries Problem Solution

HackerRank DAG Queries Problem Solution

Yashwant Parihar,

In this post, we will solve HackerRank DAG Queries Problem Solution. You are given a Directed Acyclic Graph (DAG) with n vertices and m edges. Each vertex v has an integer, a,, associated with it and the initial value of a, is 0 for all vertices. You must perform q queries on the DAG, where each query is one of the following types: 1. 1 u x: Seta, to æ for all v such that there is a path in the DAG from u to v. 2.2 u x: Seta, to æ for all v such that there is a path from u to v and a, > x. 3.3 u: Print the value of a,, on a new line.
Input Format
The first line contains three space-separated integers describing the respective values of n (the number of vertices in the DAG), m (the number of edges in the DAG), and g (the number of queries to perform).
Each of the m subsequent lines contains two space-separated integers describing the respective values of u and u (where 1 <u, v < n. uv) denoting a directed edge from vertex u to vertex in the graph.
Each of the q subsequent lines contains a query in one of the three formats described above.

Output Format

For each query of type a (i.e., 3 u), print the value of au on a new line.

Sample Input 0

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

Sample Output 0

3
3
3
3
3
2
3
2
0
0
3
2
3
2
HackerRank DAG Queries Problem Solution
HackerRank DAG Queries Problem Solution

DAG Queries C++ Solution

#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
#define forn(i,n) for (int i = 0; i < int(n); ++i)
typedef long long ll;
typedef long long i64;
typedef long double ld;
typedef pair<int, int> pii;
const int inf = int(1e9) + int(1e5);
const ll infl = ll(2e18) + ll(1e10);

#define tm suka

const int maxc = 1e9;

//const int maxn = 1001;
const int maxn = 100100;
vector<int> g[maxn];

int tm[maxn];

int qt[maxn];
int qu[maxn];
int qx[maxn];
int qans[maxn];

//const int sn = 1;
const int sn = 600;
const int sn2 = 1000;
const int block = maxn / 3 + 2;
bitset<block> bs[maxn];
bool used[maxn];
int L, R;
int n;

vector<int> ord;

void pre(int u) {
    used[u] = true;
    for (int v: g[u])
        if (!used[v])
            pre(v);
    ord.push_back(u);
}

void uin(int &a, int b) {
    a = min(a, b);
}

void uax(int &a, int b) {
    a = max(a, b);
}

int a[maxn / sn + 2][maxn];

int upd[maxn];
vector<pii> o;
void put1(int u, int x) {
    o.emplace_back(u, x);
    if (sz(o) < sn2)
        return;
    forn (i, n)
        upd[i] = -1;
    for (auto p: o)
        uax(upd[p.first], p.second);
    o.clear();
    for (int ii = n - 1; ii >= 0; --ii) {
        int u = ord[ii];
        tm[u] = max(tm[u], upd[u]);
        for (int v: g[u])
            uax(upd[v], upd[u]);
    }
}

int get1(int u) {
    int res = tm[u];
    for (auto op: o)
        if (bs[op.first][u - L])
            uax(res, op.second);
    return res;
}

vector<int> q2;

void calc2(int l, int r) {
    int k = l / sn;
    forn (i, n)
        a[k][i] = maxc;
    for (int i = l; i < r; ++i) {
        int id = q2[i];
        uin(a[k][qu[id]], qx[id]);
    }
    for (int ii = n - 1; ii >= 0; --ii) {
        int u = ord[ii];
        for (int v: g[u])
            uin(a[k][v], a[k][u]);
    }
}

int get2(int u, int l, int r) {
    l = lower_bound(q2.begin(), q2.end(), l) - q2.begin();
    r = lower_bound(q2.begin(), q2.end(), r) - q2.begin();
    int res = maxc;
    int l2 = ((l + sn - 1) / sn) * sn;
    int r2 = (r / sn) * sn;
    if (l2 > r2) {
        for (int i = l; i < r; ++i) {
            int id = q2[i];
            int v = qu[id];
            if (bs[v][u - L])
                uin(res, qx[id]);
        }
    } else {
        for (int i = l; i < l2; ++i) {
            int id = q2[i];
            int v = qu[id];
            if (bs[v][u - L])
                uin(res, qx[id]);
        }
        for (int i = r2; i < r; ++i) {
            int id = q2[i];
            int v = qu[id];
            if (bs[v][u - L])
                uin(res, qx[id]);
        }
        l2 /= sn, r2 /= sn;
        for (int i = l2; i < r2; ++i)
            uin(res, a[i][u]);
    }
    return res;
}

int main() {
    #ifdef LOCAL
    assert(freopen("test.in", "r", stdin));
    #endif
    int m, q;
    cin >> n >> m >> q;
    forn (i, m) {
        int u, v;
        scanf("%d%d", &u, &v);
        --u, --v;
        g[u].push_back(v);
    }
    forn (i, n)
        if (!used[i])
            pre(i);
    forn (i, q) {
        int t, u, x = -1;
        scanf("%d%d", &t, &u);
        --u;
        if (t != 3)
            scanf("%d", &x);
        qt[i] = t, qu[i] = u, qx[i] = x;
    }

    forn (i, q) {
        if (qt[i] != 2)
            continue;
        q2.push_back(i);
    }
    for (int i = 0; i + sn <= sz(q2); i += sn)
        calc2(i, i + sn);

    for (L = 0; L < n; L += block) {
        R = min(n, L + block);
        forn (i, n) {
            bs[i].reset();
            tm[i] = -1;
        }
        o.clear();

        forn (i, n) {
            int u = ord[i];
            if (L <= u && u < R)
                bs[u][u - L] = true;
            for (int v: g[u])
                bs[u] |= bs[v];
        }

        forn (id, q) {
            if (qt[id] == 3) {
                int u = qu[id];
                if (u < L || u >= R)
                    continue;
                int lb = get1(u);
                int val = lb >= 0 ? qx[lb] : 0;
                uin(val, get2(u, lb, id));
                qans[id] = val;
            }
            if (qt[id] == 1)
                put1(qu[id], id);
        }
    }
    forn (i, q) {
        if (qt[i] == 3)
            cout << qans[i] << '\n';
    }
}

DAG Queries Scala Solution

object Assert {
    def check(e: Boolean) {
        if (!e) {
            throw new AssertionError();
        }
    }
}

class Scanner(is: java.io.InputStream) {

    val buffer: Array[Byte] = new Array[Byte](1 << 16);

    var len: Int = 0;

    var pos: Int = 0;

    def nextChar(): Int = {
        if (pos == len) {
            val read: Int = is.read(buffer);
            if (read == -1) {
                return -1;
            }
            len = read;
            pos = 0;
        }
        Assert.check(pos < len);
        val value: Int = buffer(pos) & 0xFF;
        pos += 1;
        return value;
    }

    def nextInt(): Int = {
        var c: Int = nextChar();
        while (c == ' ' || c == '\n' || c == '\r' || c == '\t') {
            c = nextChar();
        }
        Assert.check('0' <= c && c <= '9');
        var value: Int = c - '0';
        c = nextChar();
        while ('0' <= c && c <= '9') {
            val digit: Int = c - '0';
            Assert.check(value < Int.MaxValue / 10 || value == Int.MaxValue / 10 && digit <= Int.MaxValue % 10);
            value = value * 10 + digit;
            c = nextChar();
        }
        return value;
    }
}

class IntArrayList {

    var a: Array[Int] = new Array[Int](4);

    var size: Int = 0;
    
    def add(x: Int): Unit = {
        if (size == a.length) {
            a = java.util.Arrays.copyOf(a, a.length * 2);
        }
        a(size) = x;
        size += 1;
    }
    
    def get(i: Int): Int = {
        Assert.check(i < size);
        return a(i);
    }
}

class Query(val typ: Int, val node: Int, val value: Int) {}

object Solution {

    def reorder(parents: Array[IntArrayList], queries: Array[Query]): Unit = {
        val nV: Int = parents.size;
        val startOrder: Array[Int] = new Array[Int](nV);
        {
            var i: Int = 0;
            while (i < nV) {
                startOrder(i) = i;
                i += 1;
            }
        }
        var rnd: java.util.Random = new java.util.Random(20161106);
        {
            var i: Int = nV - 1;
            while (i > 0) {
                val j: Int = rnd.nextInt(i + 1);
                val t: Int = startOrder(i);
                startOrder(i) = startOrder(j);
                startOrder(j) = t;
                i -= 1;
            }
        }
        val orderedId: Array[Int] = new Array[Int](nV);
        java.util.Arrays.fill(orderedId, -1);
        val stack: IntArrayList = new IntArrayList();
        val ip: IntArrayList = new IntArrayList();
        var nextId: Int = 0;
        {
            var i: Int = 0;
            while (i < nV) {
                if (orderedId(startOrder(i)) == -1) {
                    stack.add(startOrder(i));
                    ip.add(0);
                    while (stack.size > 0) {
                        val cur: Int = stack.a(stack.size - 1);
                        if (ip.get(ip.size - 1) == parents(cur).size) {
                            orderedId(cur) = nextId;
                            nextId += 1;
                            stack.size -= 1;
                            ip.size -= 1;
                        } else {
                            val p: Int = parents(cur).get(ip.get(ip.size - 1));
                            ip.a(ip.size - 1) += 1;
                            if (orderedId(p) == -1) {
                                stack.add(p);
                                ip.add(0);
                            }
                        }
                    }
                }
                i += 1;
            }
        }
        if (false) {
            print("new ids: ");
            var first: Boolean = true;
            {
                var i: Int = 0;
                while (i < nV) {
                    if (first) {
                        first = false;
                    } else {
                        print(", ");
                    }
                    print((i + 1) + " -> " + (orderedId(i) + 1));
                    i += 1;
                }
            }
            println();
        }
        Assert.check(nextId == nV);
        {
            var i: Int = 0;
            while (i < orderedId.length) {
                Assert.check(orderedId(i) >= 0);
                i += 1;
            }
        }
        val orderedParents: Array[IntArrayList] = new Array[IntArrayList](nV);
        {
            var i: Int = 0;
            while (i < nV) {
                orderedParents(i) = new IntArrayList();
                i += 1;
            }
        }
        {
            var i: Int = 0;
            while (i < nV) {
                {
                    var ip: Int = 0;
                    while (ip < parents(i).size) {
                        val p: Int = parents(i).get(ip);
                        orderedParents(orderedId(i)).add(orderedId(p));
                        ip += 1;
                    }
                }
                i += 1;
            }
        }
        {
            var i: Int = 0;
            while (i < nV) {
                java.util.Arrays.sort(orderedParents(i).a, 0, orderedParents(i).size);
                parents(i) = orderedParents(i);
                i += 1;
            }
        }
        {
            var i: Int = 0;
            while (i < queries.length) {
                val typ: Int = queries(i).typ;
                val node: Int = queries(i).node;
                val value: Int = queries(i).value;
                Assert.check(0 <= node && node < nV);
                queries(i) = new Query(typ, orderedId(node), value);
                i += 1;
            }
        }
    }

    def process(
        parents: Array[IntArrayList],
        queries: Array[Query],
        qFirst: Int,
        qAfter: Int,
        a: Array[Int],
        codes: Array[Long],
        add: Array[Int],
        min: Array[Int],
        result: IntArrayList
    ): Unit = {
        val nV: Int = parents.length;
        val q12: IntArrayList = new IntArrayList();
        {
            var q = qFirst;
            while (q < qAfter) {
                if (queries(q).typ < 3) {
                    q12.add(q);
                }
                q += 1;
            }
        }
        if (q12.size == 0) {
            var q: Int = qFirst;
            while (q < qAfter) {
                Assert.check(queries(q).typ == 3);
                val node: Int = queries(q).node;
                Assert.check(0 <= node && node < nV);
                result.add(a(node));
                q += 1;
            }
            return;
        }
        val n: Int = q12.size;
        Assert.check(n <= 8 * 14);
        Assert.check(nV <= 100000);
        java.util.Arrays.fill(codes, 0, nV * 2, 0);
        {
            var i: Int = 0;
            while (i < n) {
                val node: Int = queries(q12.get(i)).node;
                val word: Int = i / 56;
                val shift: Int = i % 56 / 14 * 16 + i % 14; // 14 used bits, 2 free
                codes(node * 2 + word) |= 1L << shift;
                i += 1;
            }
        }
        {
            var i: Int = 0;
            while (i < nV) {
                {
                    val pari: IntArrayList = parents(i);
                    var ip: Int = 0;
                    while (ip < pari.size) {
                        val p: Int = pari.get(ip);
                        codes((i << 1) + 0) |= codes((p << 1) + 0);
                        codes((i << 1) + 1) |= codes((p << 1) + 1);
                        ip += 1;
                    }
                }
                i += 1;
            }
        }
        var q: Int = qFirst;
        var part: Int = 0;
        while (part * 14 < n) {
            val begin: Int = part * 14;
            val end: Int = Math.min(n, begin + 14);
            val codesAdd: Int = part / 4;
            val codesShift: Int = part % 4 * 16;
            // a = Math.min(a + add, min)
            add(0) = 0;
            min(0) = 1000 * 1000 * 1000;
            var bit: Int = 0;
            while (bit < end - begin) {
                val qType: Int = queries(q12.get(begin + bit)).typ;
                val value: Int = queries(q12.get(begin + bit)).value;
                val extra: Int = 1 << bit;
                if (qType == 1) { // assign
                    var code: Int = 0;
                    while (code < extra) {
                        add(code + extra) = 1000 * 1000 * 1000;
                        min(code + extra) = value;
                        code += 1;
                    }
                } else {
                    Assert.check(qType == 2); // min
                    var code: Int = 0;
                    while (code < extra) {
                        add(code + extra) = add(code);
                        min(code + extra) = Math.min(value, min(code));
                        code += 1;
                    }
                }
                bit += 1;
            }
            var mask = 0;
            while (end == n && q != qAfter || end != n && q != q12.get(end)) {
                if (queries(q).typ < 3) {
                    mask <<= 1;
                    mask |= 1;
                } else {
                    Assert.check(queries(q).typ == 3);
                    val node: Int = queries(q).node;
                    val code: Int = ((codes((node << 1) + codesAdd) >> codesShift) & mask).toInt;
                    val answer: Int = Math.min(a(node) + add(code), min(code));
                    result.add(answer);
                }
                q += 1;
            }
            var i = 0;
            while (i < nV) {
                val code: Int = ((codes((i << 1) + codesAdd) >> codesShift) & 0xFFFF).toInt;
                a(i) = Math.min(a(i) + add(code), min(code));
                i += 1;
            }
            part += 1;
        }
    }

    def solveFast(parents: Array[IntArrayList], queries: Array[Query]): IntArrayList = {
        val nV: Int = parents.length;
        {
            var i: Int = 0;
            while (i < nV) {
                {
                    var ip: Int = 0;
                    while (ip < parents(i).size) {
                        val p: Int = parents(i).get(ip);
                        Assert.check(p < i); // parents before children
                        ip += 1;
                    }
                }
                i += 1;
            }
        }
        val a: Array[Int] = new Array[Int](nV);
        val codes: Array[Long] = new Array[Long](100000 * 2);
        val add: Array[Int] = new Array[Int](1 << 14);
        val min: Array[Int] = new Array[Int](1 << 14);
        val result: IntArrayList = new IntArrayList();
        val MAX12Q = 8 * 14;
        var first: Int = 0;
        var n12q: Int = 0;
        val nQ: Int = queries.length;
        {
            var i: Int = 0;
            while (i < nQ) {
                if (queries(i).typ < 3) {
                    n12q += 1;
                }
                if (n12q == MAX12Q || i == nQ - 1) {
                    process(parents, queries, first, i + 1, a, codes, add, min, result);
                    first = i + 1;
                    n12q = 0;
                }
                i += 1;
            }
        }
        return result;
    }

    def main(args: Array[String]): Unit = {
        val in: Scanner = new Scanner(System.in);
        val nV: Int = in.nextInt();
        val nE: Int = in.nextInt();
        val nQ: Int = in.nextInt();
        val parents: Array[IntArrayList] = new Array[IntArrayList](nV);
        {
            var i: Int = 0;
            while (i < nV) {
                parents(i) = new IntArrayList();
                i += 1;
            }
        }
        {
            var i: Int = 0;
            while (i < nE) {
                val parent: Int = in.nextInt() - 1;
                val child: Int = in.nextInt() - 1;
                parents(child).add(parent);
                i += 1;
            }
        }
        val queries: Array[Query] = new Array[Query](nQ);
        {
            var i: Int = 0;
            while (i < nQ) {
                val qType: Int = in.nextInt();
                if (qType == 1 || qType == 2) {
                    val parent: Int = in.nextInt() - 1;
                    val value: Int = in.nextInt();
                    queries(i) = new Query(qType, parent, value);
                } else {
                    Assert.check(qType == 3);
                    val node: Int = in.nextInt() - 1;
                    queries(i) = new Query(qType, node, -1);
                }
                i += 1;
            }
        }
        reorder(parents, queries);
        val result: IntArrayList = solveFast(parents, queries);
        {
            var i: Int = 0;
            while (i < result.size) {
                println(result.get(i));
                i += 1;
            }
        }
    }
}

DAG Queries Java Solution

import java.io.*;
import java.util.*;

public class Solution {

  static class MyBitSet {
    private final static int ADDRESS_BITS_PER_WORD = 6;
    private long[] words;
    private transient int wordsInUse = 0;

    private static int wordIndex(int bitIndex) {
      return bitIndex >> ADDRESS_BITS_PER_WORD;
    }

    public MyBitSet(int nbits) {
      words = new long[wordIndex(nbits - 1) + 1];
    }

    public void clear() {
      while (wordsInUse > 0)
        words[--wordsInUse] = 0;
    }

    public void set(int bitIndex) {
      int wordIndex = wordIndex(bitIndex);
      expandTo(wordIndex);
      words[wordIndex] |= (1L << bitIndex);
    }

    private void expandTo(int wordIndex) {
      int wordsRequired = wordIndex + 1;
      if (wordsInUse < wordsRequired) {
        wordsInUse = wordsRequired;
      }
    }


    public void or(MyBitSet set) {
      int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);

      if (wordsInUse < set.wordsInUse) {
        wordsInUse = set.wordsInUse;
      }

      for (int i = 0; i < wordsInCommon; i++) {
        words[i] |= set.words[i];
      }

      if (wordsInCommon < set.wordsInUse) {
        System.arraycopy(set.words, wordsInCommon, words, wordsInCommon,
            wordsInUse - wordsInCommon);
      }
    }

    public boolean get(int bitIndex) {
      int wordIndex = wordIndex(bitIndex);
      return (wordIndex < wordsInUse) && ((words[wordIndex] & (1L << bitIndex)) != 0);
    }
  }

  static class PS {
    int opt;
    int u;
    int x;
    int i;
  }

  static class QS {
    int u;
    int i;

    public QS(int u, int i) {
      this.u = u;
      this.i = i;
    }
  }

  static Set<Integer>[] graph;
  static int[] indeg;
  static int[] topo;
  static int ttot = 1;

  static void topo_dfs(int node) {
    topo[ttot++] = node;
    for (int i = ptr[node]; i > 0; i = nxt[i]) {
      if (--indeg[succ[i]] == 0) {
        topo_dfs(succ[i]);
      }
    }
  }

  static int[] nxt;
  static int[] succ;
  static int[] ptr;
  static int index = 1;

  static void addedge(int u, int v) {
    nxt[index] = ptr[u];
    ptr[u] = index;
    succ[index++] = v;
  }


  static final int B = 316;

  static int[] solve2(int[][] queries, int n, int nQue) {
    int q = queries[0].length - 1;
    int[] ans = new int[q + 1];

    QS[] que = new QS[nQue + 1];
    PS[] perform = new PS[q + 1];
    int ptot = 0;
    int qtot = 0;

    for (int i = 1; i <= q; i++) {
      perform[ptot] = new PS();
      perform[ptot].opt = queries[0][i];
      if (perform[ptot].opt <= 2) {
        perform[ptot].u = queries[1][i];
        perform[ptot].x = queries[2][i];
        perform[ptot++].i = i;
      } else {
        que[qtot++] = new QS(queries[1][i], i);
      }
      ans[i] = Integer.MAX_VALUE;
    }

    MyBitSet[] b = new MyBitSet[n + 1];
    for (int i = n; i > 0; i--) {
      b[i] = new MyBitSet(320);
    }

    boolean[] cover = new boolean[n + 1];
    int[] minVal = new int[n + 1];

    for (int l = (ptot - 1) - (ptot - 1) % B, r = ptot - 1; l >= 0; r = l - 1, l -= B) {
      for (int i = n; i > 0; i--) {
        b[i].clear();
      }

      for (int i = l; i <= r; ++i) {
        b[perform[i].u].set(i - l);
      }

      for (int i = 1; i <= n; i++) {
        for (int j = ptr[topo[i]]; j > 0; j = nxt[j]) {
          b[succ[j]].or(b[topo[i]]);
        }
      }

      Arrays.fill(cover, false);

      for (int i = l; i <= r; i++) {
        if (perform[i].opt == 1) {
          cover[perform[i].u] = true;
        }
      }

      for (int i = 1; i <= n; i++) {
        if (cover[topo[i]]) {
          for (int j = ptr[topo[i]]; j > 0; j = nxt[j]) {
            cover[succ[j]] = true;
          }
        }
      }

      Arrays.fill(minVal, Integer.MAX_VALUE);

      for (int i = l; i <= r; i++) {
        if (perform[i].opt == 2) {
          minVal[perform[i].u] = Math.min(minVal[perform[i].u], perform[i].x);
        }
      }

      for (int i = 1; i <= n; ++i) {
        for (int j = ptr[topo[i]]; j > 0; j = nxt[j]) {
          minVal[succ[j]] = Math.min(minVal[succ[j]], minVal[topo[i]]);
        }
      }


      int i = qtot;
      while (i > 0 && que[i - 1].i > perform[l].i) {
        i--;
      }
      while (i < qtot) {
        if (que[i].i < perform[r].i) {
          int j = r;
          while (perform[j].i > que[i].i) {
            --j;
          }
          for (; j >= l; j--)
            if (b[que[i].u].get(j - l)) {
              ans[que[i].i] = Math.min(ans[que[i].i], perform[j].x);
              if (perform[j].opt == 1) {
                --qtot;
                QS temp = que[i];
                que[i] = que[qtot];
                que[qtot] = temp;
                break;
              }
            }
          i += j < l ? 1 : 0;
        } else if (cover[que[i].u]) {
          int j = r;
          for (; perform[j].opt == 2 || !b[que[i].u].get(j - l); j--) {
            if (perform[j].opt == 2 && b[que[i].u].get(j - l)) {
              ans[que[i].i] = Math.min(ans[que[i].i], perform[j].x);
            }
          }
          ans[que[i].i] = Math.min(ans[que[i].i], perform[j].x);

          --qtot;
          QS temp = que[i];
          que[i] = que[qtot];
          que[qtot] = temp;

        } else {
          ans[que[i].i] = Math.min(ans[que[i].i], minVal[que[i].u]);
          i++;
        }

      }
    }
    while (qtot-- > 0) {
      ans[que[qtot].i] = 0;
    }
    return ans;
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    StringTokenizer st = new StringTokenizer(br.readLine());

    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());
    int q = Integer.parseInt(st.nextToken());

    graph = new Set[n + 1];
    Set<Integer>[] parent = new Set[n + 1];

    for (int i = 1; i <= n; i++) {
      graph[i] = new HashSet<>();
      parent[i] = new HashSet<>();
    }

    for (int i = 0; i < m; i++) {
      st = new StringTokenizer(br.readLine());
      int u = Integer.parseInt(st.nextToken());
      int v = Integer.parseInt(st.nextToken());
      graph[u].add(v);
      parent[v].add(u);
    }

    int[][] queries = new int[3][q + 1];
    int[] convert = new int[n + 1];
    int nodes = 0;
    int op3 = 0;

    for (int i = 1; i <= q; i++) {
      st = new StringTokenizer(br.readLine());
      queries[0][i] = Integer.parseInt(st.nextToken());
      int u = Integer.parseInt(st.nextToken());

      if (convert[u] == 0) {
        nodes++;
        convert[u] = nodes;
      }

      queries[1][i] = convert[u];
      if (queries[0][i] <= 2) {
        int x = Integer.parseInt(st.nextToken());
        queries[2][i] = x;
      } else {
        op3++;
      }
    }

    for (int u = 1; u <= n; u++) {
      if (convert[u] == 0) {
        for (int v : parent[u]) {
          graph[v].remove(u);
          graph[v].addAll(graph[u]);
        }
        for (int v : graph[u]) {
          parent[v].remove(u);
          parent[v].addAll(parent[u]);
        }
        
        parent[u] = null;
        graph[u] = null;
      }
    }

    indeg = new int[nodes + 1];
    boolean[] existDeg = new boolean[nodes + 1];

    nxt = new int[m + 1];
    ptr = new int[nodes + 1];
    succ = new int[m + 1];

    for (int u1 = 1; u1 <= n; u1++) {
      int u = convert[u1];
      if (u > 0) {
        for (int v1 : graph[u1]) {
          int v = convert[v1];
          indeg[v]++;
          existDeg[v] = true;
          addedge(u, v);
        }
      }
    }

    topo = new int[nodes + 1];
    for (int i = nodes; i > 0; i--) {
      if (!existDeg[i]) {
        topo_dfs(i);
      }
    }

    int[] ans = solve2(queries, nodes, op3);

    for (int i = 1; i <= q; i++) {
      if (ans[i] < Integer.MAX_VALUE) {
        bw.write(ans[i] + "\n");
      }
    }

    bw.close();
    br.close();
  }
}
C++ HackerRank Solutions java Scala