BFS - 1012번: 유기농 배추

import sys
from collections import deque


t = int(sys.stdin.readline())

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def bfs(x, y, visited, m, n, maps):
    q = deque()
    visited.add((x, y))
    q.append((x, y))

    while q:
        a, b = q.popleft()
        
        for i in range(4):
            na, nb = a + dx[i], b + dy[i]

            if 0 <= na < m and 0 <= nb < n and maps[nb][na] == 1 and (na, nb) not in visited:
                q.append((na, nb))
                visited.add((na, nb))

    return
    


for _ in range(t):

    line = list(map(int, sys.stdin.readline().split()))
    m, n, k = line[0], line[1], line[2]

    maps = [[0] * m for _ in range(n)]
    cabbs = [] # 양배추 좌표 리스트

    # 양배추 좌표 입력받기
    for i in range(k):
        x, y = map(int, sys.stdin.readline().split())

        maps[y][x] = 1
        cabbs.append((x, y))


    visited = set()
    cnt = 0

    for x, y in cabbs:
        if (x, y) not in visited:
            bfs(x, y, visited, m, n, maps)
            cnt += 1

    
    print(cnt)