inspirit941

def solution(routes):
    # 도로의 맨 앞에서부터 감시카메라 설치.
    routes = [[i[0], i[1]] for i in sorted(routes, key = lambda x: (x[0]))]
    result = [routes.pop(0)]
    for compare in routes:
        idx = 0
        while idx != len(result):
            # 만약 새 차량의 진입시점 / 진출시점이 기존 카메라 설치 범위에 들어간다면
            if (result[idx][0] <= compare[0] <= result[idx][1]) or (result[idx][0] <= compare[1] <= result[idx][1]):
                # 감시카메라가 새 차량을 감지할 수 있도록 감시카메라의 위치 조정

inspirit941

def check(result):
    for x, y, kind in result:
        # 기둥인 경우
        if kind == 0:
            if y == 0 or [x-1, y, 1] in result or [x, y, 1] in result or [x, y-1, 0] in result:
                continue
            else:
                return False
        elif kind == 1:
            if [x, y-1, 0] in result or [x+1, y-1, 0] in result or \

inspirit941

def check(result):
    for x, y, kind in result:
        # 기둥인 경우
        if kind == 0:
            if y == 0 or (x-1, y, 1) in result or (x, y, 1) in result or (x, y-1, 0) in result:
                continue
            else:
                return False
        # 보인 경우
        elif kind == 1:

inspirit941

def solution(begin, target, words):
    if target not in set(words):
        return 0
    queue = [begin]
    total_count = 0
    while len(words) != 0:
        for value in queue:
            # 바꾸게 될 단어를 저장하는 변수
            temp = []
            for word in words:

inspirit941

import sys
import heapq
N, M = map(int, sys.stdin.readline().split())
maps = []
for _ in range(M):
    maps.append(list(sys.stdin.readline()))
visited = [[0 for _ in range(N)] for _ in range(M)]

def bfs(start, maps, visited):
    dirs = [(1,0),(0,1),(0,-1),(-1,0)]

inspirit941

import sys
from collections import deque
height, width = map(int, sys.stdin.readline().split())
maps = []
waters = []
for y in range(height):
    arr = sys.stdin.readline()
    for x in range(len(arr)):
        if arr[x] == 'S':
            # 시작 지점

inspirit941

def solution(triangle):
    # 첫째 줄은 index가 0이므로, 둘째 줄부터 계산한다.
    for rows in range(1, len(triangle)):
        # 각 줄의 index 값별로 비교한다.
        for idx in range(rows + 1):
            # 가장 왼쪽 값인 경우
            if idx == 0:
                triangle[rows][idx] += triangle[rows-1][idx]
            # 가장 오른쪽 값인 경우
            elif idx == rows:

inspirit941

def make_base(numbers, base, table):
    temp = []
    if numbers == 0:
        return "0"
    while numbers != 0:
        numbers, r = divmod(numbers, base)
        temp.append(str(r))
    # n진법으로 변환한 문자열을 n진수로 바꾼 뒤 문자열 형태로 리턴
    return "".join([str(table[int(i)]) for i in temp[::-1]])

inspirit941

import sys
import heapq
height, width = map(int, sys.stdin.readline().split())
maps = []
for _ in range(height):
    maps.append(sys.stdin.readline())

# 벽을 부수고 방문했는지, 아닌지에 따라 최단거리가 달라질 수 있으므로 
# visited는 부수지 않고 지나감 / 부수고 지나감 두 가지가 필요하다. 
# 따라서 visited[y][x][벽 파괴여부] 형태로 선언한다.

inspirit941

# 이진수로 만들기
def make_binary(n):
    temp = []
    while n != 0:
        n, r = divmod(n, 2)
        temp.append(str(r))
    return "".join(temp[::-1])
def solution(n):
    count_one = make_binary(n).count("1")
    # 현재 숫자에서 +1씩 증가하며