CodeEff/ECCO huggingface dataset:
# Original solution
from collections import deque
import sys

N_MAX = 200000 + 5

H, W, K = list(map(int, input().split()))
sth, stw, glh, glw = list(map(int, input().split()))

INF = 10**6 * K

dp = [[INF for _ in range(W+2)] for _ in range(H+2)]

dp[0] = [-1]*(W+2)
dp[H+1] = [-1]*(W+2)
for h in range(1, H+1):
    s = sys.stdin.readline()
    dp[h][0] = -1
    dp[h][W+1] = -1
    for w in range(1, W+1):
        if s[w-1] == "@":
            dp[h][w] = -1

dp[sth][stw] = 0


# Seen = [[INF]*W for _ in range(H)]
XY = {(1, 0), (-1, 0), (0, 1), (0, -1)}


def bfs(sth, stw, glh, glw):
    next_q = deque()
    next_q.append((sth, stw))

    while len(next_q) != 0:
        # キュー取り出し(先頭)
        h, w = next_q.popleft()
        for dh, dw in XY:
            for sk in range(1, K+1):
                hs, ws = h + dh*sk, w + dw*sk
                if dp[hs][ws] == -1:
                    break
                if dp[hs][ws] == INF:
                    next_q.append((hs, ws))
                    dp[hs][ws] = dp[h][w] + 1
                # elif dp[hs][ws] <= dp[h][w]:
                #    break
                if hs == glh and ws == glw:
                    return dp[h][w] + 1
    return -1


def main():
    ret = bfs(sth, stw, glh, glw)
    print(ret)


if __name__ == '__main__':
    main()


# Optimized solution
from collections import deque
import sys

N_MAX = 200000 + 5

H, W, K = list(map(int, input().split()))
sth, stw, glh, glw = list(map(int, input().split()))

INF = 10**6 * K

dp = [[INF for _ in range(W + 2)] for _ in range(H + 2)]

dp[0] = [-1] * (W + 2)
dp[H + 1] = [-1] * (W + 2)
for h in range(1, H + 1):
    s = sys.stdin.readline()
    dp[h][0] = -1
    dp[h][W + 1] = -1
    for w in range(1, W + 1):
        if s[w - 1] == "@":
            dp[h][w] = -1

dp[sth][stw] = 0


# Seen = [[INF]*W for _ in range(H)]
XY = {(1, 0), (-1, 0), (0, 1), (0, -1)}


def bfs(sth, stw, glh, glw):
    next_q = deque()
    next_q.append((sth, stw))

    while len(next_q) != 0:
        # キュー取り出し(先頭)
        h, w = next_q.popleft()
        for dh, dw in XY:
            for sk in range(1, K + 1):
                hs, ws = h + dh * sk, w + dw * sk
                if dp[hs][ws] == -1:
                    break
                if dp[hs][ws] == INF:
                    next_q.append((hs, ws))
                    dp[hs][ws] = dp[h][w] + 1
                elif dp[hs][ws] <= dp[h][w]:
                    # もし、dp[hs][ws] が 今の値以下なら
                    # その先はdp[hs][ws]をもとに 書き込まれている or 今後書き込まれる ので止める
                    break
                # if hs == glh and ws == glw:
                #    return dp[h][w] + 1
    # return -1


def main():
    bfs(sth, stw, glh, glw)

    if dp[glh][glw] == INF:
        print((-1))
    else:
        print((dp[glh][glw]))


if __name__ == '__main__':
    main()
# Original solution
h,a,*m=open(0)
h,w,k,a,b,f,g=list(map(int,(h+a).split()))
d=[I:=h*w]*I
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j;p=d[s]+1
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<p:break
   if d[t]==I:q+=t,;d[t]=p
print((d[~w+f*w+g]%I-1))

# Optimized solution
h,a,*m=open(0)
h,w,k,a,b,f,g=list(map(int,(h+a).split()))
I=h*w
d=[I]*I
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j;p=d[s]+1
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print((d[~w+f*w+g]%I-1))
# Original solution
h,a,*m=open(0)
h,w,k,a,b,f,g=list(map(int,(h+a).split()))
d=[I:=h*w]*I
m+=d,
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print((d[~w+f*w+g]%I-1))

# Optimized solution
h,a,*m=open(0)
h,w,k,a,b,f,g=list(map(int,(h+a).split()))
I=h*w
d=[I]*I
m+=d,
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print((d[~w+f*w+g]%I-1))
# Original solution
h,a,*m=open(0)
h,w,k,a,b,f,g=list(map(int,(h+a).split()))
I=h*w
d=[I]*I
m+=d,
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   q+=t,;d[t]=p
print((d[~w+f*w+g]%I-1))

# Optimized solution
h,a,*m=open(0)
h,w,k,a,b,f,g=list(map(int,(h+a).split()))
d=[I:=h*w]*I
m+=d,
q=[a:=~w+a*w+b]
d[a]=1
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   if'.'!=m[(i:=s//w+y*~z)][(j:=s%w+x*~z)]or(p:=d[s]+1)>d[(t:=i*w+j)]:break
   if d[t]>p:q+=t,;d[t]=p
print((d[~w+f*w+g]%I-1))
# Original solution
h,a,*m=open(0)
h,w,k,a,b,f,g=list(map(int,(h+a).split()))
d=[I:=h*w]*I
m+=d,
q=[a:=~w+a*w+b]
d[a]=1
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   if'.'!=m[(i:=s//w+y*~z)][(j:=s%w+x*~z)]or(p:=d[s]+1)>d[(t:=i*w+j)]:break
   if d[t]>p:q+=t,;d[t]=p
print((d[~w+f*w+g]%I-1))

# Optimized solution
h,a,*m=open(0)
h,w,k,a,b,f,g=list(map(int,(h+a).split()))
d=[I:=h*w]*I
m+=d,
q=[a:=~w+a*w+b]
d[a]=1
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   if'.'!=m[(i:=s//w+y*~z)][(j:=s%w+x*~z)]or d[s]>=d[(t:=i*w+j)]:break
   if-~d[s]<d[t]:q+=t,;d[t]=d[s]+1
print((d[~w+f*w+g]%I-1))
# Original solution
y=1,0,-1,0,1
h,a,*m=open(0)
h,w,k,a,b,f,g=list(map(int,(h+a).split()))
d=[I:=h*w]*I
m+=d,
q=[a:=~w+a*w+b]
d[a]=1
for s in q:
 for x in range(4):
  for z in range(k):
   if'.'!=m[(i:=s//w+y[x]*~z)][(j:=s%w+y[x+1]*~z)]or(p:=d[s]+1)>d[(t:=i*w+j)]:break
   if d[t]>p:q+=t,;d[t]=p
print((d[~w+f*w+g]%I-1))

# Optimized solution
h,a,*m=open(0)
h,w,k,a,b,f,g=list(map(int,(h+a).split()))
I=h*w
d=[I]*I
m+=d,
a=~w+a*w+b
q=[a]
d[a]=1
for s in q:
 for x in range(4):
  for z in range(k):
   y=~z,0,z+1,0,~z;i,j=s//w+y[x],s%w+y[x+1];t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print((d[~w+f*w+g]%I-1))
# Original solution
h,a,*m=open(0)
h,w,k,a,b,f,g=list(map(int,(h+a).split()))
d=[I:=h*w]*I
m+=d,
q=[a:=~w+a*w+b]
d[a]=1
for s in q:
 for x in 0,1,2,3:
  for z in range(k):
   y=~z,0,z+1,0,~z;i,j=s//w+y[x],s%w+y[x+1];t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print((d[~w+f*w+g]%I-1))

# Optimized solution
h,a,*m=open(0)
h,w,k,a,b,f,g=list(map(int,(h+a).split()))
I=h*w
d=[I]*I
m+=d,
a=~w+a*w+b
q=[a]
d[a]=1
for s in q:
 for x in 0,1,2,3:
  for z in range(k):
   y=~z,0,z+1,0;i,j=s//w+y[x],s%w+y[x^1];t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print((d[~w+f*w+g]%I-1))
# Original solution
h,a,*m=open(0)
h,w,k,a,b,f,g=list(map(int,(h+a).split()))
d=[I:=h*w]*I
m+=d,
q=[a:=~w+a*w+b]
d[a]=1
for s in q:
 for x in range(4):
  for z in range(k):
   y=~z,0,z+1,0;i,j=s//w+y[x],s%w+y[x^1];t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print((d[~w+f*w+g]%I-1))

# Optimized solution
h,a,*m=open(0)
h,w,k,a,b,f,g=list(map(int,(h+a).split()))
I=h*w
d=[I]*I
m+=d,
a=~w+a*w+b
q=[a]
d[a]=1
for s in q:
 for x in 0,1,2,3:
  for z in range(k):
   y=~z,0,z+1,0;i,j=s//w+y[x],s%w+y[~x];t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print((d[~w+f*w+g]%I-1))
# Original solution
h,a,*m=open(0)
h,w,k,a,b,f,g=list(map(int,(h+a).split()))
d=[I:=h*w]*I
m+=d,
q=[a:=~w+a*w+b]
d[a]=1
for s in q:
 for x in 0,1,2,3:
  for z in range(k):
   y=0,~z,0,z+1;i,j=s//w+y[x],s%w+y[~x];t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print((d[~w+f*w+g]%I-1))

# Optimized solution
h,a,*m=open(0)
h,w,k,a,b,f,g=list(map(int,(h+a).split()))
d=[I:=h*w]*I
m+=d,
q=[a:=~w+a*w+b]
d[a]=1
for s in q:
 for x in 0,1,2,3:
  for z in range(k):
   y=z+1,0,~z,0;i,j=s//w+y[x],s%w+y[~x];t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print((d[~w+f*w+g]%I-1))
# Original solution
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import collections
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    dist = [[INF] * W for _ in range(H)]
    q = collections.deque([(x1, y1)])
    dist[x1][y1] = 0
    while q:
        i, j = q.popleft()
        d = dist[i][j]
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            for dt in range(1, K + 1):
                ni, nj = i + di * dt, j + dj * dt
                if not (0 <= ni < H and 0 <= nj < W): break
                if C[ni][nj] == '@': break
                if dist[ni][nj] <= d + 1: continue
                dist[ni][nj] = d + 1
                q.append((ni, nj))
    ans = dist[x2][y2]
    if ans == INF:
        print((-1))
    else:
        print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = list(map(int, input().split()))
    x1, y1, x2, y2 = [int(x) - 1 for x in input().split()]
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)


# Optimized solution
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import collections
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    dist = [[INF] * W for _ in range(H)]
    q = collections.deque([(x1, y1)])
    dist[x1][y1] = 0
    while q:
        i, j = q.popleft()
        d = dist[i][j]
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            for dt in range(1, K + 1):
                ni, nj = i + di * dt, j + dj * dt
                if not (0 <= ni < H and 0 <= nj < W): break
                if C[ni][nj] == '@': break
                if dist[ni][nj] == d + 1: continue
                if dist[ni][nj] < d + 1: break
                dist[ni][nj] = d + 1
                q.append((ni, nj))
    ans = dist[x2][y2]
    if ans == INF:
        print((-1))
    else:
        print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = list(map(int, input().split()))
    x1, y1, x2, y2 = [int(x) - 1 for x in input().split()]
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)
# Original solution
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from heapq import heappush, heappop
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    dist = [[INF] * W for _ in range(H)]
    q = [(0, x1, y1)]
    dist[x1][y1] = 0
    while q:
        d, i, j = heappop(q)
        if dist[i][j] < d: continue
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            for dt in range(1, K + 1):
                ni, nj = i + di * dt, j + dj * dt
                if not (0 <= ni < H and 0 <= nj < W): break
                if C[ni][nj] == '@': break
                if dist[ni][nj] <= d + 1: continue
                heappush(q, (d + 1, ni, nj))
                dist[ni][nj] = d + 1
    ans = dist[x2][y2]
    if ans == INF:
        print((-1))
    else:
        print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = list(map(int, input().split()))
    x1, y1, x2, y2 = [int(x) - 1 for x in input().split()]
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)


# Optimized solution
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from heapq import heappush, heappop
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    dist = [[INF] * W for _ in range(H)]
    q = [(0, x1, y1)]
    dist[x1][y1] = 0
    while q:
        d, i, j = heappop(q)
        if dist[i][j] < d: continue
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            for dt in range(1, K + 1):
                ni, nj = i + di * dt, j + dj * dt
                if not (0 <= ni < H and 0 <= nj < W): break
                if C[ni][nj] == '@': break
                if dist[ni][nj] == d + 1: continue
                if dist[ni][nj] < d + 1: break
                heappush(q, (d + 1, ni, nj))
                dist[ni][nj] = d + 1
    ans = dist[x2][y2]
    if ans == INF:
        print((-1))
    else:
        print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = list(map(int, input().split()))
    x1, y1, x2, y2 = [int(x) - 1 for x in input().split()]
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)
# Original solution
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    H, W, K = list(map(int, rl().split()))
    sy, sx, gy, gx = [int(n) - 1 for n in rl().split()]
    c = [rl().rstrip() for _ in range(H)]
    
    INF = 10 ** 10
    cost = [[INF] * W for _ in range(H)]
    cost[sy][sx] = 0
    que = deque([(sy, sx)])
    while que:
        cy, cx = que.popleft()
        for dy, dx in ((-1, 0), (0, 1), (1, 0), (0, -1)):
            for k in range(1, K + 1):
                ny, nx = cy + k * dy, cx + k * dx
                if 0 <= ny < H and 0 <= nx < W:
                    if c[ny][nx] == '@':
                        break
                    if cost[ny][nx] <= cost[cy][cx]:
                        break
                    cost[ny][nx] = cost[cy][cx] + 1
                    que.append((ny, nx))
    print((cost[gy][gx] if cost[gy][gx] != INF else -1))


if __name__ == '__main__':
    solve()


# Optimized solution
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    H, W, K = list(map(int, rl().split()))
    sy, sx, gy, gx = [int(n) - 1 for n in rl().split()]
    c = [rl().rstrip() for _ in range(H)]
    
    INF = 10 ** 10
    cost = [[INF] * W for _ in range(H)]
    cost[sy][sx] = 0
    que = deque([(sy, sx)])
    while que:
        cy, cx = que.popleft()
        for dy, dx in ((-1, 0), (0, 1), (1, 0), (0, -1)):
            for k in range(1, K + 1):
                ny, nx = cy + k * dy, cx + k * dx
                if 0 <= ny < H and 0 <= nx < W:
                    if c[ny][nx] == '@':
                        break
                    if cost[ny][nx] <= cost[cy][cx]:
                        break
                    ncost = cost[cy][cx] + 1
                    if ncost < cost[ny][nx]:
                        cost[ny][nx] = ncost
                        que.append((ny, nx))
    print((cost[gy][gx] if cost[gy][gx] != INF else -1))


if __name__ == '__main__':
    solve()
# Original solution
h,w,k=map(int,input().split())
r,s,t,u=map(lambda x:int(x)-1,input().split())
b=[input()for _ in range(h)]
l=[[-1]*w for _ in range(h)]
l[r][s]=0
from collections import*
d=deque([(r,s)])
while d:
  x,y=d.popleft()
  if(x==t)&(y==u):exit(print(l[x][y]))
  for e,f in [[1,0],[-1,0],[0,-1],[0,1]]:
    for i in range(1,k+1):
      p,q=x+e*i,y+f*i
      if not(0<=p<h and 0<=q<w)or b[p][q]=="@":break
      if 0<=l[p][q]<=l[x][y]:break
      if l[p][q]==-1:d+=[(p,q)]
      l[p][q]=l[x][y]+1
print(-1)


# Optimized solution
h,w,k=map(int,input().split())
r,s,t,u=map(lambda x:int(x)-1,input().split())
b=[input()for _ in range(h)]
l=[[-1]*w for _ in range(h)]
l[r][s]=0
from collections import*
d=deque([(r,s)])
while d:
  x,y=d.popleft()
  if(x==t)&(y==u):exit(print(l[x][y]))
  for e,f in[[1,0],[-1,0],[0,-1],[0,1]]:
    for i in range(1,k+1):
      p,q=x+e*i,y+f*i
      if not((0<=p<h)&(0<=q<w))or b[p][q]=="@":break
      if 0<=l[p][q]<=l[x][y]:break
      if l[p][q]==-1:d+=[(p,q)];l[p][q]=l[x][y]+1
print(-1)
# Original solution
z,v,a=input,range,print
h,w,k=map(int,z().split())
r,s,t,u=map(lambda x:int(x)-1,z().split())
b=[z()for _ in v(h)]
l=[[-1]*w for _ in v(h)]
l[r][s]=0
from collections import*
d=deque([(r,s)])
while d:
  x,y=d.popleft()
  if(x==t)&(y==u):exit(a(l[x][y]))
  for e,f in[[1,0],[-1,0],[0,-1],[0,1]]:
    for i in v(1,k+1):
      p,q=x+e*i,y+f*i
      if not((0<=p<h)&(0<=q<w))or b[p][q]=="@" or 0<=l[p][q]<=l[x][y]:break
      d+=[(p,q)];l[p][q]=l[x][y]+1
a(-1)


# Optimized solution
from collections import*
z,v,a=input,range,print
h,w,k=map(int,z().split());r,s,t,u=map(lambda x:int(x)-1,z().split())
b=[z()for _ in v(h)];l=[[-1]*w for _ in v(h)];l[r][s]=0
d=deque([(r,s)])
while d:
  x,y=d.popleft()
  if(x==t)&(y==u):exit(a(l[x][y]))
  for e,f in[[1,0],[-1,0],[0,-1],[0,1]]:
    for i in v(1,k+1):
      p,q=x+e*i,y+f*i
      if not((0<=p<h)&(0<=q<w))or b[p][q]=="@" or 0<=l[p][q]<=l[x][y]:break
      if l[p][q]<0:d+=[(p,q)];l[p][q]=l[x][y]+1
a(-1)
# Original solution
from collections import*
z,v,a=input,range,print
h,w,k=map(int,z().split());r,s,t,u=map(lambda x:int(x)-1,z().split())
b=[z()for _ in v(h)];l=[[-1]*w for _ in v(h)];l[r][s]=0
d=deque([(r,s)])
while d:
  x,y=d.popleft()
  if(x==t)&(y==u):exit(a(l[x][y]))
  for e,f in[[1,0],[-1,0],[0,-1],[0,1]]:
    for i in v(1,k+1):
      p,q=x+e*i,y+f*i
      if not((0<=p<h)&(0<=q<w))or b[p][q]=="@" or 0<=l[p][q]<=l[x][y]:break
      if l[p][q]<0:d+=[(p,q)];l[p][q]=l[x][y]+1
a(-1)


# Optimized solution
from collections import*
z,v,a=input,range,print
h,w,k=map(int,z().split());r,s,t,u=map(lambda x:int(x)-1,z().split())
b=[z()for _ in v(h)];l=[[-1]*w for _ in v(h)];l[r][s]=0
d=deque([(r,s)])
while d:
  x,y=d.popleft();j=l[x][y]
  if(x==t)&(y==u):exit(a(j))
  for e,f in[[1,0],[-1,0],[0,-1],[0,1]]:
    for i in v(1,k+1):
      p,q=x+e*i,y+f*i
      if not((0<=p<h)&(0<=q<w))or b[p][q]=="@" or 0<=l[p][q]<=j:break
      if l[p][q]<0:d+=[(p,q)];l[p][q]=j+1
a(-1)
# Original solution
# Acceptance of input

import sys

file_input = sys.stdin

V, E = list(map(int, file_input.readline().split()))

adj_mat = [[0] * V for i in range(V)]

for line in file_input:
    u, v, c = list(map(int, line.split()))
    adj_mat[u][v] = c

# Ford???Fulkerson algorithm

import collections

# BFS for residual capacity network
def bfs(start, goal, parent):
    unvisited = [True] * V
    queue = collections.deque()
    queue.append(start)
    unvisited[start] = False
    while queue:
        u = queue.popleft()
        for v, flow in enumerate(adj_mat[u]):
            if unvisited[v] and (flow > 0):
                queue.append(v)
                unvisited[v] = False
                parent[v] = u
    return not unvisited[goal]

def ford_fulkerson(source, sink):
    parent = [None] * V
    max_flow = 0
    while bfs(source, sink, parent):
        aug_path_flow = 10000
        v = sink
        while (v != source):
            aug_path_flow = min(aug_path_flow, adj_mat[parent[v]][v])
            v = parent[v]
        max_flow += aug_path_flow
        v = sink
        while (v != source):
            u = parent[v]
            adj_mat[u][v] -= aug_path_flow
            adj_mat[v][u] += aug_path_flow
            v = u
    return max_flow

# output
print((ford_fulkerson(0, V - 1)))

# Optimized solution
# Acceptance of input

import sys

file_input = sys.stdin

V, E = list(map(int, file_input.readline().split()))

adj_mat = [[0] * V for i in range(V)]

for line in file_input:
    u, v, c = list(map(int, line.split()))
    adj_mat[u][v] = c

# Ford???Fulkerson algorithm

import collections

# BFS for residual capacity network
def bfs(start, goal, parent):
    flow = [0] * V
    queue = collections.deque()
    queue.append(start)
    flow[start] = 10000
    while queue:
        u = queue.popleft()
        for v, r_capacity in enumerate(adj_mat[u]):
            if not flow[v] and (r_capacity > 0):
                queue.append(v)
                flow[v] = min(flow[u], r_capacity)
                parent[v] = u
                if v == goal:
                    return flow[goal]

def ford_fulkerson(source, sink):
    max_flow = 0
    while True:
        parent = [None] * V
        aug_path_flow = bfs(source, sink, parent)
        if aug_path_flow:
            max_flow += aug_path_flow
            v = sink
            while (v != source):
                u = parent[v]
                adj_mat[u][v] -= aug_path_flow
                adj_mat[v][u] += aug_path_flow
                v = u
        else:
            break
    return max_flow

# output
print((ford_fulkerson(0, V - 1)))
# Original solution
from sys import stdin
from collections import defaultdict
readline = stdin.readline



#readline = open('???.txt').readline

def main():
    v, e = list(map(int, readline().split()))
    g = defaultdict(list)
    residual = [[0] * v for _ in range(v)]
    source, sink = 0, v - 1

    for _ in range(e):
        s, t, c = list(map(int, readline().split()))
        if 0 < c:
            g[s].append(t)
            g[t].append(s)
            residual[s][t] = c

    capacity = sum(residual[source][i] for i in g[source])

    while True:
        route, flow = search(g, residual, source, sink)
        if route is None:
            break
        for i in range(1, len(route)):
            residual[route[i - 1]][route[i]] -= flow
            residual[route[i]][route[i - 1]] += flow
    print((capacity - sum(residual[source][i] for i in g[source])))

def search(g, residual, source, sink):
    dfs_stack = [(source, None, float('inf'))]
    route = [None]
    visited = set()
    while dfs_stack:
        u, prev, flow = dfs_stack.pop()
        while route[-1] != prev:
            route.pop()
        route.append(u)
        visited |= {u}
        if u == sink:
            return route[1:], flow
        for v in g[u]:
            if v in route:
                continue
            next_flow = min(residual[u][v], flow)
            if 0 < next_flow:
                dfs_stack.append((v, u, next_flow))
    return None, None
main()

# Optimized solution
from sys import stdin
from collections import defaultdict
readline = stdin.readline


def main():
    v, e = list(map(int, readline().split()))
    g = defaultdict(set)
    residual = [[0] * v for _ in range(v)]
    source, sink = 0, v - 1

    for _ in range(e):
        s, t, c = list(map(int, readline().split()))
        if 0 < c and s != sink and t != source:
            g[s] |= {t}
            g[t] |= {s}
            residual[s][t] = c

    while True:
        route, flow = search(g, residual, source, sink)
        if not route:
            break
        for s, t in zip(route, route[1:]):
            residual[s][t] -= flow
            residual[t][s] += flow

    print((sum(residual[sink][i] for i in g[sink])))


def search(g, residual, source, sink):
    dfs_stack = [(source, None, float('inf'))]
    route = [None]
    visited = set()
    while dfs_stack:
        u, prev, flow = dfs_stack.pop()
        while route[-1] != prev:
            route.pop()
        route.append(u)
        visited |= {u}
        if u == sink:
            return route[1:], flow
        for v in g[u]:
            if v not in visited and 0 < residual[u][v]:
                dfs_stack.append((v, u, min(residual[u][v], flow)))
    return [], 0
main()