1555_F. Good Graph_150
You have an undirected graph consisting of n vertices with weighted edges.

A simple cycle is a cycle of the graph without repeated vertices. Let the weight of the cycle be the [XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) of weights of edges it consists of.

Let's say the graph is good if all its simple cycles have weight 1. A graph is bad if it's not good.

Initially, the graph is empty. Then q queries follow. Each query has the next type: 

  * u v x — add edge between vertices u and v of weight x if it doesn't make the graph bad. 



For each query print, was the edge added or not.

Input

The first line contains two integers n and q (3 ≤ n ≤ 3 ⋅ 10^5; 1 ≤ q ≤ 5 ⋅ 10^5) — the number of vertices and queries.

Next q lines contain queries — one per line. Each query contains three integers u, v and x (1 ≤ u, v ≤ n; u ≠ v; 0 ≤ x ≤ 1) — the vertices of the edge and its weight.

It's guaranteed that there are no multiple edges in the input.

Output

For each query, print YES if the edge was added to the graph, or NO otherwise (both case-insensitive).

Example

Input


9 12
6 1 0
1 3 1
3 6 0
6 2 0
6 4 1
3 4 1
2 4 0
2 5 0
4 5 0
7 8 1
8 9 1
9 7 0


Output


YES
YES
YES
YES
YES
NO
YES
YES
NO
YES
YES
NO
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.PrintStream;
import java.util.Arrays;
import java.util.Iterator;
import java.util.Random;
import java.util.Stack;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Vector;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author sarthakmanna
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        FGoodGraph solver = new FGoodGraph();
        solver.solve(1, in, out);
        out.close();
    }

    static class FGoodGraph {
        public void solve(int testNumber, FastReader in, PrintWriter out) {
            int i, j, k;

            int N = in.nextInt(), M = in.nextInt();
            ArrayList<Integer>[] graph = new ArrayList[N];
            for (i = 0; i < N; ++i) graph[i] = new ArrayList<>();

            ArrayList<Edge> tree = new ArrayList<>(), cycle = new ArrayList<>();
            DSU dsu = new DSU(N);
            boolean[] ans = new boolean[M];
            for (i = 0; i < M; ++i) {
                Edge edge = new Edge(i, in.nextInt() - 1, in.nextInt() - 1, in.nextInt());
                if (dsu.isConnected(edge.getU(), edge.getV())) {
                    cycle.add(edge);
                } else {
                    dsu.addEdge(edge.getU(), edge.getV());
                    graph[edge.getU()].add(edge.getV());
                    graph[edge.getV()].add(edge.getU());

                    tree.add(edge);
                    ans[i] = true;
                }
            }

            HashSet<Integer> roots = new HashSet<>();
            boolean[] vis = new boolean[N];
            for (i = 0; i < N; ++i)
                if (!vis[i]) {
                    roots.add(i);
                    dfs(i, vis, graph);
                }

            HLD_LCA hld_lca = new HLD_LCA(tree.toArray(new Edge[tree.size()]), N, roots);
            for (Edge edge : cycle) {
                if ((edge.getWeight() ^ hld_lca.pathQuery(edge.getU(), edge.getV())) == 1) {
                    ans[edge.i] = true;
                    hld_lca.pathUpdate(edge.getU(), edge.getV(), +1);
                }
            }

            for (boolean val : ans) out.println(val ? "YES" : "NO");
        }

        void dfs(int node, boolean[] v, ArrayList<Integer>[] graph) {
            if (v[node]) return;
            v[node] = true;
            for (int itr : graph[node]) dfs(itr, v, graph);
        }

    }

    static class Helper {
        public final long MOD;
        public final int MAXN;
        final Random rnd;

        public Helper() {
            MOD = 1000_000_007;
            MAXN = 1000_006;
            rnd = new Random();
        }

        public Helper(long mod, int maxn) {
            MOD = mod;
            MAXN = maxn;
            rnd = new Random();
        }

        public int getRandomInRange(int l, int r) {
            return rnd.nextInt(r - l + 1) + l;
        }

    }

    static class DSU {
        int N;
        int[] parent;
        int[] size;

        public DSU(int nodeCount) {
            N = nodeCount;
            parent = new int[nodeCount];
            Arrays.fill(parent, -7);
            size = new int[nodeCount];
            Arrays.fill(size, 1);
        }

        public int getParent(int node) {
            if (parent[node] < 0) return node;
            else return parent[node] = getParent(parent[node]);
        }

        public boolean isConnected(int a, int b) {
            return getParent(a) == getParent(b);
        }

        public void addEdge(int a, int b) {
            a = getParent(a);
            b = getParent(b);
            if (a == b) {
                return;
            } else if (size[a] > size[b]) {
                a ^= b;
                b ^= a;
                a ^= b;
            }
            parent[a] = b;
            size[b] += size[a];
            size[a] = -7;
        }

    }

    static class FastReader {
        static final int BUFSIZE = 1 << 20;
        static byte[] buf;
        static int index;
        static int total;
        static InputStream in;

        public FastReader(InputStream is) {
            try {
                in = is;
                buf = new byte[BUFSIZE];
            } catch (Exception e) {
            }
        }

        private int scan() {
            try {
                if (index >= total) {
                    index = 0;
                    total = in.read(buf);
                    if (total <= 0)
                        return -1;
                }
                return buf[index++];
            } catch (Exception | Error e) {
                System.err.println(e.getMessage());
                return 13 / 0;
            }
        }

        public int nextInt() {
            int c, val = 0;
            for (c = scan(); c <= 32; c = scan()) ;
            boolean neg = c == '-';
            if (c == '-' || c == '+')
                c = scan();
            for (; c >= '0' && c <= '9'; c = scan())
                val = (val << 3) + (val << 1) + (c & 15);
            return neg ? -val : val;
        }

    }

    static class HLD_LCA {
        static final int defaultValue = 0;
        ArrayList<Integer>[] graph;
        int[] depth;
        int[] parent;
        int[] chCount;
        int[] queue;
        int N;
        int[] weight;
        HashSet<Integer> roots;
        SegmentTree st;
        int[] treePos;
        int[] linearTree;
        int[] segRoot;

        public HLD_LCA(Edge[] edges, int n, HashSet<Integer> r) {
            int i;
            N = n;
            roots = r;

            graph = new ArrayList[N];
            for (i = 0; i < N; ++i) graph[i] = new ArrayList<>();

            for (Edge e : edges) {
                graph[e.u].add(e.v);
                graph[e.v].add(e.u);
            }
            iterativeDFS();

            weight = new int[N];
            for (Edge e : edges) {
                int child = depth[e.u] > depth[e.v] ? e.u : e.v;
                weight[child] = e.weight;
            }

            HLDify();
        }

        public int operate(int a, int b) {
            return a ^ b;
        }

        private void iterativeDFS() {
            parent = new int[N];
            depth = new int[N];
            chCount = new int[N];
            queue = new int[N];
            Arrays.fill(chCount, 1);

            int i, st = 0, end = 0;
            for (int root : roots) {
                parent[root] = -1;
                depth[root] = 1;
                queue[end++] = root;
            }

            while (st < end) {
                int node = queue[st++], h = depth[node] + 1;
                Iterator<Integer> itr = graph[node].iterator();
                while (itr.hasNext()) {
                    int ch = itr.next();
                    if (depth[ch] > 0) continue;
                    depth[ch] = h;
                    parent[ch] = node;
                    queue[end++] = ch;
                }
            }
            for (i = N - 1; i >= 0; --i)
                if (!roots.contains(queue[i]))
                    chCount[parent[queue[i]]] += chCount[queue[i]];
        }

        private void HLDify() {
            int i, j, treeRoot = -7;

            treePos = new int[N];
            linearTree = new int[N];
            segRoot = new int[N];

            Stack<Integer> stack = new Stack<>();
            stack.ensureCapacity(N << 1);
            stack.addAll(roots);
            for (i = 0; !stack.isEmpty(); ++i) {
                int node = stack.pop();
                if (i == 0 || linearTree[i - 1] != parent[node])
                    treeRoot = node;
                linearTree[i] = node;
                treePos[node] = i;
                segRoot[node] = treeRoot;

                int bigChild = -7, bigChildPos = -7, lastPos = graph[node].size() - 1;
                for (j = 0; j < graph[node].size(); ++j) {
                    int tempNode = graph[node].get(j);
                    if (tempNode == parent[node]) continue;
                    if (bigChild < 0 || chCount[bigChild] < chCount[tempNode]) {
                        bigChild = tempNode;
                        bigChildPos = j;
                    }
                }
                if (bigChildPos >= 0) {
                    int temp = graph[node].get(lastPos);
                    graph[node].set(lastPos, bigChild);
                    graph[node].set(bigChildPos, temp);
                }

                for (int itr : graph[node])
                    if (parent[node] != itr)
                        stack.push(itr);
            }

            int[] respectiveWeights = new int[N];
            for (i = 0; i < N; ++i)
                respectiveWeights[i] = weight[linearTree[i]];
            st = new SegmentTree(respectiveWeights, 0, 0);
        }

        public int pathQuery(int node1, int node2) {
            int ret = defaultValue, temp;
            while (segRoot[node1] != segRoot[node2]) {
                if (depth[segRoot[node1]] > depth[segRoot[node2]]) {
                    node1 ^= node2;
                    node2 ^= node1;
                    node1 ^= node2;
                }

                temp = st.rangeQuery(treePos[segRoot[node2]], treePos[node2]);
                ret = operate(ret, temp);
                node2 = parent[segRoot[node2]];
            }

            if (treePos[node1] > treePos[node2]) {
                node1 ^= node2;
                node2 ^= node1;
                node1 ^= node2;
            }
            temp = st.rangeQuery(treePos[node1] + 1, treePos[node2]);   // ...treePos[node1] + 1... for Edge Query
            ret = operate(ret, temp);

            return ret;
        }

        public void pathUpdate(int node1, int node2, int value) {
            while (segRoot[node1] != segRoot[node2]) {
                if (depth[segRoot[node1]] > depth[segRoot[node2]]) {
                    node1 ^= node2;
                    node2 ^= node1;
                    node1 ^= node2;
                }
                st.rangeUpdate(treePos[segRoot[node2]], treePos[node2], value);
                node2 = parent[segRoot[node2]];
            }
            if (treePos[node1] > treePos[node2]) {
                node1 ^= node2;
                node2 ^= node1;
                node1 ^= node2;
            }
            st.rangeUpdate(treePos[node1] + 1, treePos[node2], value);     // ...treePos[node1] + 1... for Edge Update
        }

    }

    static class SegmentTree {
        int N;
        int[] tree;
        Helper hp = new Helper();

        public SegmentTree(int[] ar, int def_node, int def_lazy) {
            N = ar.length + 1;
            tree = new int[N];

            for (int i = 0; i < ar.length; ++i) pointUpdate(i, ar[i]);
        }

        public void pointUpdate(int idx, int val) {
            ++idx;
            while (idx < N) {
                tree[idx] ^= val;
                idx += idx & -idx;
            }
        }

        public void rangeUpdate(int l, int r, int val) {
            for (int i = l; i <= r; ++i) {
                pointUpdate(i, hp.getRandomInRange(0, Integer.MAX_VALUE >> 1));
            }
        }

        public int prefixQuery(int idx) {
            ++idx;
            int ret = 0;
            while (idx > 0) {
                ret ^= tree[idx];
                idx -= idx & -idx;
            }
            return ret;
        }

        public int rangeQuery(int l, int r) {
            int ret = prefixQuery(r);
            if (l > 0) ret ^= prefixQuery(l - 1);
            return ret;
        }

    }

    static class Edge {
        public int i;
        public int u;
        public int v;
        int weight;

        public int getU() {
            return u;
        }

        public int getV() {
            return v;
        }

        public int getWeight() {
            return weight;
        }

        public Edge(int id, int a, int b, int wt) {
            i = id;
            u = a;
            v = b;
            weight = wt;
        }

        public String toString() {
            return "(" + u + ", " + v + " -> " + weight + ")";
        }

    }
}
