Python 재귀 쓸 때 필수

sys.setrecursionlimit(10**6)
# default: 1000로 매우 얕은 편

4번이나 RecursionError를 겪고서야 떠올랐던 재귀 깊이

'''
1. 50 * 50 * 2500
2500 * 2500 = 6,250,000
1,000,000,000, O(N)

2. 완전탐색 안되고 희소배열 백트래킹 하려고했지만? 그냥 재귀로
''''

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def dfs(x, y):
    if x < 0 or y < 0 or x >= N or y >= M:
        return
    if g[x][y] == False:
        return
    g[x][y] = False
    dfs(x, y + 1)
    dfs(x, y - 1)
    dfs(x + 1, y)
    dfs(x - 1, y)

T = int(input())
for _ in range(T):
    M, N, K = map(int, input().split())
    cnt = 0
    g = [[False] * M for _ in range(N)]
    
    for _ in range(K):
        X, Y = map(int, input().split())
        g[Y][X] = True
        
    for i in range(N):
        for j in range(M):
            if g[i][j]:
                dfs(i, j)
                cnt += 1
    print(cnt)