"""
Aim: Given an undirected graph and an integer M. The task is to determine if 
     the graph can be colored with at most M colors such that no two adjacent 
     vertices of the graph are colored with the same color.
Intuition: We consider all the different combinations of the colors for the 
           given graph using backtacking. 

"""


def isSafe(graph, v, n, temp, color):
    # This checks whether if it safe to color the given node with temp color i.e checking if the adjacent nodes are different from temp
    for i in range(v):
        if graph[n][i] == 1 and color[i] == temp:
            return False
    return True


def check(graph, m, v, n, color):
    # This function iteratively checks different combinations.
    if n == v:  # base case : if all the nodes are traversed return
        return True
    for i in range(1, m + 1):
        if isSafe(graph, v, n, i, color):  # checking if it is safe to color
            color[n] = i
            if check(graph, m, v, n + 1, color):
                return True
            color[n] = 0
    return False


def graphcoloring(graph, M, V):
    color = [0] * (V + 1)  # assigning colors to different nodes
    return check(graph, M, V, 0, color)


# ------------------------DRIVER CODE ------------------------


def main():
    for _ in range(int(input())):
        V = int(input())
        M = int(input())
        E = int(input())
        list = [int(x) for x in input().strip().split()]
        graph = [[0 for i in range(V)] for j in range(V)]
        cnt = 0
        for i in range(E):
            graph[list[cnt] - 1][list[cnt + 1] - 1] = 1
            graph[list[cnt + 1] - 1][list[cnt] - 1] = 1
            cnt += 2
        if graphcoloring(graph, M, V) == True:
            print(1)
        else:
            print(0)


if __name__ == "__main__":
    main()

"""
Sample Input:
2
4
3
5
1 2 2 3 3 4 4 1 1 3
3
2
3
1 2 2 3 1 3

Sample Output:
1
0

"""

"""
Aim: Given an undirected graph and an integer M. The task is to determine if 
     the graph can be colored with at most M colors such that no two adjacent 
     vertices of the graph are colored with the same color.
Intuition: We consider all the different combinations of the colors for the 
           given graph using backtacking. 

"""


def isSafe(graph, v, n, temp, color):
    # This checks whether if it safe to color the given node with temp color i.e checking if the adjacent nodes are different from temp
    for i in range(v):
        if graph[n][i] == 1 and color[i] == temp:
            return False
    return True


def check(graph, m, v, n, color):
    # This function iteratively checks different combinations.
    if n == v:  # base case : if all the nodes are traversed return
        return True
    for i in range(1, m + 1):
        if isSafe(graph, v, n, i, color):  # checking if it is safe to color
            color[n] = i
            if check(graph, m, v, n + 1, color):
                return True
            color[n] = 0
    return False


def graphcoloring(graph, M, V):
    color = [0] * (V + 1)  # assigning colors to different nodes
    return check(graph, M, V, 0, color)


# ------------------------DRIVER CODE ------------------------


def main():
    for _ in range(int(input())):
        V = int(input())
        M = int(input())
        E = int(input())
        list = [int(x) for x in input().strip().split()]
        graph = [[0 for i in range(V)] for j in range(V)]
        cnt = 0
        for i in range(E):
            graph[list[cnt] - 1][list[cnt + 1] - 1] = 1
            graph[list[cnt + 1] - 1][list[cnt] - 1] = 1
            cnt += 2
        if graphcoloring(graph, M, V) == True:
            print(1)
        else:
            print(0)


if __name__ == "__main__":
    main()

"""
Sample Input:
2
4
3
5
1 2 2 3 3 4 4 1 1 3
3
2
3
1 2 2 3 1 3

Sample Output:
1
0

"""

Aim: Given an undirected graph and an integer M. The task is to determine if       the graph can be colored with at most M colors such that no two adjacent       vertices of the graph are colored with the same color. Intuition: We consider all the different combinations of the colors for the             given graph using backtacking. # This checks whether if it safe to color the given node with temp color i.e checking if the adjacent nodes are different from temp # This function iteratively checks different combinations. # base case : if all the nodes are traversed return # checking if it is safe to color # assigning colors to different nodes # ------------------------DRIVER CODE ------------------------ Sample Input: 2 4 3 5 1 2 2 3 3 4 4 1 1 3 3 2 3 1 2 2 3 1 3  Sample Output: 1 0