Gears in a machine

Alice and Bob are working on a new contraption to make the most of their extended summer vacations. However, they ran into some trouble with the mechanics of their machine, specifically, in the gear trains. The complicated meshing of gears has confused them and they require your help to make it functional.

A gear train is a network of gears that are engaged with each other. Mechanically, two gears are said to be engaged or connected if some segment of their teeth interlocks, so that rotating gear forces the rotation of the other gear. This mechanism forces all gears that are engaged with the latter gear to rotate and this motion propagates throughout the train. This type of network can be described in terms of a graph where each vertex represents a gear and an edge denotes that two gears are engaged. 

There are two types of gears, internal and external. The types of gears depend on which region their teeth are present. Note that all gears are fixed to their position.

Example:

Input:
8 8 3
1 1 1 1 1 1 1 1
1 2
1 3
2 4
3 4
4 5
6 7
7 8
8 6
1 5 1 1
1 5 1 -1
6 7 1 1
Output:
NO
YES
NO

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class GearsInMachine {
    static long mod = 998244353;

    static long pro(long a, long b) {
        return (a % mod * b % mod) % mod;
    }

    static long add(long a, long b) {
        return (a + b) % mod;
    }

    static int maxn = 200005;

    static int pow(int n) {
        return (int) (Math.log10(n) / Math.log10(2));
    }

    static List<Integer> list[] = new ArrayList[maxn];
    static int p[] = new int[maxn];

    public static void main(String args[]) {
        int n = 8;
        int m = 8;
        int q = 3;
        int a[] = { 1, 1, 1, 1, 1, 1, 1, 1 };
        int a1[][] = { { 1, 2 }, { 1, 3 }, { 2, 4 }, { 3, 4 }, { 4, 5 }, { 6, 7 }, { 7, 8 }, { 8, 6 } };
        int a2[][] = { { 1, 5, 1, 1 }, { 1, 5, 1, -1 }, { 6, 7, 1, 1 } };

        for (int i = 0; i < n; i++) {
            list[i] = new ArrayList<>();
            p[i] = a[i];
        }

        for (int i = 0; i < m; i++) {
            int u = a1[i][0] - 1;
            int v = a1[i][1] - 1;
            list[u].add(v);
            list[v].add(u);
        }
        int comp[] = new int[n];
        boolean isbipar[] = new boolean[n + 1];
        int side[] = new int[n];
        Arrays.fill(side, -1);
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (side[i] == -1) {
                cnt++;
                side[i] = 0;
                Queue<Integer> qq = new LinkedList<>();
                qq.add(i);
                boolean res = true;
                while (!qq.isEmpty()) {
                    int t = qq.poll();
                    comp[t] = cnt;
                    for (int v : list[t]) {
                        int d = p[v] + p[t];
                        if (side[v] == -1) {
                            if (d == 0)
                                side[v] = side[t];
                            else
                                side[v] = side[t] ^ 1;
                            qq.add(v);
                        } else
                            res &= ((d != 0 && side[t] != side[v]) || (d == 0 && side[v] == side[t]));
                    }
                }
                isbipar[cnt] = res;
            }
        }
        for (int k = 0; k < q; k++) {
            int u = a2[k][0] - 1;
            int v = a2[k][1] - 1;
            int d1 = a2[k][2];
            int d2 = a2[k][3];
            if (comp[u] != comp[v]) {
                if (!isbipar[comp[u]] || !isbipar[comp[v]])
                    System.out.println("NO");
                else
                    System.out.println("YES");
            } else {
                if (!isbipar[comp[u]])
                    System.out.println("NO");
                else {
                    if ((d1 == d2 && side[u] == side[v]) || (d1 != d2 && side[u] != side[v]))
                        System.out.println("YES");
                    else
                        System.out.println("NO");
                }
            }
        }
    }
}