Not The Huge Users Community Society (NTHUCS) is designing a new online game where people open shops to serve other people in a virtual world. In this game, each user needs to select a virtual country where he/she belongs to. Also, there is a map where each user needs to find a place to open his/her own shop (such as a restaurant, a post office, a bank, etc) to serve other people. Some parts of the map are reserved for the landscapes and the features, such as bridges, rivers, forests, remains …, etc. The remaining parts are empty spots that can be used for the shops. There are also roads in the map, each road joining two empty spots. To increase the interaction between people from different countries, we wish to restrict that the two owners of the shops on the same road cannot be from the same country.
Eventually, each spot in the map will be occupied by some person. Your task is to write a program to check if there is at least a way that users can select their belonging countries so that the restriction can be followed.
The first line of input contains a positive integer t (t <= 20), which indicates how many maps to check. For each map, the first line contains three positive integers n, m, k (n <= 50, m <= n*(n-1)/2, k <= n), indicating that there are n spots for opening shops (a spot is numbered from 1 to n) in the map, m roads, and people can select from one of the k countries. In next m lines, each line contains two integers u and v, which indicate the two end spots of a road.
For each map, output a line with “Yes” if this map can be used for this online game. Otherwise, output a line with “No”.