Hamiltonian Path Detection

You are given a directed graph, and you need to determine whether the graph contains a Hamiltonian Path. A Hamiltonian path is a path that visits each vertex exactly once.

For each test case, you are given the number of vertices N, the number of edges M, followed by a list of directed edges. Your task is to output "Yes" if a Hamiltonian path exists, and "No" otherwise.

The problem requires exploring possible paths using Depth First Search (DFS) or backtracking methods.

inputFormat

The first line of input contains a single integer T (the number of test cases). Each test case is described as follows:

1. The first line contains two space‐separated integers: N (the number of vertices) and M (the number of edges).
2. Then M lines follow, each containing two space‐separated integers u and v denoting a directed edge from vertex u to vertex v.

Vertices are labeled from 1 to N.

outputFormat

For each test case, output a single line containing "Yes" if there exists a Hamiltonian Path in the graph; otherwise output "No".

1
4 4
1 2
2 3
3 4
4 1

Yes