백준 1012번 유기농 배추

import sys

input = sys.stdin.readline
sys.setrecursionlimit(100000)

move = [[1, 0], [0, 1], [-1, 0], [0, -1]]


def dfs(x, y):
    visited[x][y] = True
    for a, b in move:
        nx = x + a
        ny = y + b
        if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and board[nx][ny] == 1:
            dfs(nx, ny)


t = int(input())

while t:
    t -= 1
    m, n, k = map(int, input().split())
    board = [[0] * m for _ in range(n)]

    for _ in range(k):
        y, x = map(int, input().split())
        board[x][y] = 1

    visited = [[False] * m for _ in range(n)]
    count = 0
    for i in range(n):
        for j in range(m):
            if board[i][j] == 0 or visited[i][j]:
                continue
            count += 1
            dfs(i, j)
    print(count)