Aryan loves graph theory more than anything. Well, no, he likes to flex his research paper on line graphs to everyone more. To start a conversation with you, he decides to give you a problem on line graphs. In the mathematical discipline of graph theory, the line graph of a simple undirected graph (G) is another simple undirected graph (L(G)) that represents the adjacency between every two edges in (G). Precisely speaking, for an undirected graph (G) without self-loops or multiple edges, its line graph (L(G)) is a graph such that Each vertex of (L(G)) represents an edge of (G). Two vertices of (L(G)) are adjacent if and only if their corresponding edges share a common endpoint in (G). Also, (L^0(G)=G) and (L^k(G)=L(L^{k-1}(G))) for (k\geq 1). An Euler trail is a sequence of edges that visits every edge of the graph exactly once. This trail can be either a path (starting and ending at different vertices) or a cycle (starting and ending at the same vertex). Vertices may be revisited during the trail, but each edge must be used exactly once. Aryan gives you a simple connected graph (G) with (n) vertices and (m) edges and an integer (k), and it is guaranteed that (G) has an Euler trail and it is not a path graph(^{\text{∗}}). He asks you to determine if (L^k(G)) has an Euler trail. (^{\text{∗}})A path graph is a tree where every vertex is connected to atmost two other vertices. Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 10^4)). The description of the test cases follows. The first line of each test case contains three space-separated integers (n), (m), and (k) ((5 \le n \le 2 \cdot 10^5), (n-1 \le m \le \min(\frac{n\cdot(n-1)}{2} ,2 \cdot 10^5)), (1 \le k \le 2 \cdot 10^5)). The next (m) lines of each test case contain two space-separated integers (u) and (v) ($$$1 \le u,v \le