Even Weight Path in an Undirected Graph

You are given an undirected weighted graph with n vertices and m edges. Your task is to determine whether there exists a path from vertex 1 to vertex n such that the sum of the weights along the path is even.

More formally, for each test case, you are given a graph \(G\) with vertices \(1, 2, \ldots, n\) and a set of edges. Each edge is specified by three integers \(u, v, w\), representing an undirected edge between vertices \(u\) and \(v\) with weight \(w\). Determine if there exists a path from vertex 1 to vertex n so that the total weight \(W\) satisfies \(W \equiv 0 \pmod{2}\).

Note: The graph can contain cycles and multiple edges. It is guaranteed that \(1 \leq u, v \leq n\) and \(w\) is a positive integer.

inputFormat

The input is read from standard input. The first line contains a single integer \(T\) denoting the number of test cases. For each test case, the first line contains two integers \(n\) and \(m\) representing the number of vertices and edges respectively. This is followed by \(m\) lines, each containing three integers \(u\), \(v\), and \(w\) that describe an undirected edge.

For example:

1
5 6
1 2 3
1 3 4
2 3 5
2 4 1
3 4 2
4 5 6

outputFormat

For each test case, print a single line containing either "YES" if there exists a path from vertex 1 to vertex n with an even total weight, or "NO" otherwise.

For example:

YES

## sample

1
5 6
1 2 3
1 3 4
2 3 5
2 4 1
3 4 2
4 5 6

YES

</p>