AT_agc077_c [AGC077C] Reverse and DAG

There is a simple directed graph $ G $ with $ N $ vertices and $ M $ edges. The vertices are numbered $ 1 $ through $ N $ , and the $ i $ -th edge goes from vertex $ a_i $ to vertex $ b_i $ . It is guaranteed that $ (a_i,b_i)\neq (b_j,a_j) $ for $ i\neq j $ . Also, an integer $ K $ with $ 2 \leq K \leq N-2 $ is given. Determine whether it is possible to make $ G $ a graph with no directed cycles (DAG) by performing the following operation zero or more times. - Choose a size- $ K $ subset $ S $ of $ \lbrace 1,\ldots,N\rbrace $ . For every directed edge whose both endpoints' numbers are in $ S $ , reverse its direction. - That is, if there is an edge from vertex $ u $ to vertex $ v\ (u,v\in S) $ , delete that edge and add a directed edge from vertex $ v $ to vertex $ u $ . This operation is performed simultaneously for all applicable edges. $ T $ test cases are given; solve each of them.

The input is given from Standard Input in the following format: > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ Each test case is given in the following format: > $ N $ $ M $ $ K $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ $ \vdots $ $ a_M $ $ b_M $

Output the answers for $ \mathrm{case}_1,\mathrm{case}_2,\ldots,\mathrm{case}_T $ in this order in the following format. Output `Yes` if it is possible to make $ G $ a graph with no directed cycles (DAG) by performing the operation zero or more times, and `No` otherwise.

### Sample Explanation 1 In the first test case, $ G $ can be made into a graph with no directed cycles by performing the following two operations. - In the first operation, perform the operation with $ S = \lbrace 1, 2,7 \rbrace $ . The directed edges whose both endpoints' numbers are in $ S $ are the edge from vertex $ 1 $ to vertex $ 2 $ and the edge from vertex $ 7 $ to vertex $ 1 $ . The directions of these edges are reversed. - In the second operation, perform the operation with $ S = \lbrace 4, 5,7 \rbrace $ . The directed edge whose both endpoints' numbers are in $ S $ is the edge from vertex $ 4 $ to vertex $ 5 $ . The direction of this edge is reversed, and $ G $ becomes a graph with no directed cycles. In the second test case, it is impossible to make $ G $ a graph with no directed cycles regardless of the operations performed. ### Constraints - $ 1 \leq T \leq 50000 $ - $ 4 \leq N \leq 2\times 10^5 $ - $ 0 \leq M \leq \min({N(N-1), 2\times 10^5}) $ - $ 2 \leq K \leq N-2 $ - $ 1 \leq a_i, b_i \leq N $ - $ a_i \neq b_i $ - $ (a_i, b_i) \neq (a_j, b_j) $ and $ (a_i,b_i) \neq (b_j,a_j) $ for $ i\neq j $ . - The sum of $ N $ in each input is at most $ 2\times 10^5 $ . - The sum of $ M $ in each input is at most $ 2\times 10^5 $ . - All input values are integers.