qwe

2937

Hegra
DayDreamer124
Az_dream
SYNUACM
clearmann
ji_suan_ji
Kusoul
pio

star_sky

takanasi
acwing_9072

Coincidence233
Renjianzdscs

from collections import defaultdict,deque
from sys import stdin
from heapq import heappush,heappop

g = defaultdict(list)
n,m = map(int,input().split())
dist = [float('inf')] * (n+1)
st = [False for _ in range(n+1)]
def djikstra():
q = [[0,1]]
dist[1] = 0
while q:
_,w = heappop(q)
if st[w]:
continue
st[w] = True
for u,d in g[w]:
if dist[u] > dist[w] + d:
dist[u] = dist[w] + d;
heappush(q,[dist[u],u])
return dist[n] if dist[n] != float('inf') else -1

for _ in range(m):
g[a].append((b,c))

print(djikstra())


from sys import stdin
from collections import defaultdict
n,m = map(int,input().split())
g = defaultdict(list)
dist = [float('inf')] * (n+1)
st = [False] * (n+1)
def djikstra(n):
dist[1] = 0
for i in range(n-1):
t = -1
for j in range(n):
if not st[j] and (t == -1 or dist[t]>dist[j]):
t = j
st[t] = True
for w,d in g[t]:
dist[w] = min(dist[w],dist[t] + d)

return dist[n] if dist[n] != float('inf') else -1

for _ in range(m):
a,b,c = map(int,input().split())
g[a].append((b,c))

print(djikstra(n))


from collections import defaultdict,deque

n,m = map(int,input().split())
g = defaultdict(list)
d = [0] * (n+1)
def topsort(n):
q = deque()
for i in range(1,n+1):
if not d[i]:
q.append(i)
ans = []
while q:
w = q.popleft()
ans.append(w)
for u in g[w]:
d[u] -= 1
if not d[u]:
q.append(u)
if len(ans) == n:
print(" ".join(map(str,ans)))
else:
print(-1)

for _ in range(m):
a,b = map(int,input().split())
d[b] += 1
g[a].append(b)
topsort(n)


n,m = map(int,input().split())
h = [-1] * (n+1);ne = [0] * (m+1);e = [0]*(m+1)
idx = 0
q = [0] * (n+1);d =[-1]*(n+1)
global idx
e[idx] = b;ne[idx] = h[a];h[a] = idx
idx += 1

def bfs():
hh = 0;tt =0
q[0] = 1
d[1] = 0
while hh <= tt:
w = q[hh];hh+=1
i = h[w]
while i != -1:
j = e[i]
if d[j] == -1:
d[j] = d[w] + 1
q[tt+1] = j;tt += 1
i = ne[i]
return d[n]
for _ in range(m):
a,b = map(int,input().split())
print(bfs())



n = int(input())
h = [-1] * (2*n+10);ne = [0] * (2*n+10);e = [0]*(2*n+10)
idx = 0;ans = n
st = [False]*(n+1)
global idx
e[idx] = b;ne[idx] = h[a];h[a] = idx;
idx += 1

def dfs(u):
global n,ans
res = 0;Sum = 0;
i = h[u];st[u] = True

while i!=-1:
j = e[i];
i = ne[i]
if st[j]:
continue
s = dfs(j);Sum += s;
res = max(res,s)

res = max(res,n-Sum - 1)
ans = min(ans,res)
return Sum + 1

for _ in range(n-1):
a,b = map(int,input().split())
dfs(1)
print(ans)



from collections import deque
n,m = map(int,input().split())
g = [input().split() for _ in range(n)]

def bfs(g):
global n,m
st = [[False for _ in range(m)] for i in range(n)]
q = deque([(0,0)])
step  = 0
st[0][0] = True
while q:
size = len(q)
for _ in range(size):
i,j = q.popleft()
if i == n - 1 and j == m - 1:
return step

for dx,dy in [[1,0],[-1,0],[0,-1],[0,1]]:
x,y = dx + i,dy + j
if x == n or y == m or x<0 or y<0 or st[x][y] or g[x][y] == '1':
continue
st[x][y] = True

q.append([x,y])
step += 1
return -1
print(bfs(g))


n = int(input())

g = [['.' for i in range(n)] for j in range(n)]
col = [False]*n;left = [False]*(2*n-1)
right = [False]*(2*n-1)

def dfs(i):
global n
if i == n:
for j in g:
print(''.join(j))
print()
return

for j in range(n):
if col[j] or left[i+j] or right[j-i+n-1]:
continue
col[j],left[i+j],right[j-i+n-1] = True,True,True
g[i][j] = 'Q'
dfs(i+1)
col[j],left[i+j],right[j-i+n-1] = False,False,False
g[i][j] = '.'

dfs(0)


from copy import deepcopy
n = int(input())
ans = []

def dfs(i,n,mark,t):
if i > n:
print(" ".join(map(str,t)))

return
for j in range(1,n+1):
if mark>>j&1:
continue
t.append(j)
dfs(i+1,n,mark|(1<<j),t)
t.pop()

dfs(1,n,0,[])


#include <iostream>

using namespace std;

const int N = 50010;

int n, m;
int p[N], d[N];

int find(int x)
{
if (p[x] != x)
{
int t = find(p[x]);
d[x] += d[p[x]];
p[x] = t;
}
return p[x];
}

int main()
{
scanf("%d%d", &n, &m);

for (int i = 1; i <= n; i ++ ) p[i] = i;

int res = 0;
while (m -- )
{
int t, x, y;
scanf("%d%d%d", &t, &x, &y);

if (x > n || y > n) res ++ ;
else
{
int px = find(x), py = find(y);
if (t == 1)
{
if (px == py && (d[x] - d[y]) % 3) res ++ ;
else if (px != py)
{
p[px] = py;
d[px] = d[y] - d[x];
}
}
else
{
if (px == py && (d[x] - d[y] - 1) % 3) res ++ ;
else if (px != py)
{
p[px] = py;
d[px] = d[y] + 1 - d[x];
}
}
}
}

printf("%d\n", res);

return 0;
}



n,m = map(int,input().split())
s = input().strip()
hash = [0] * (n+ 1)
p = [1] * (n+1)
MOD = 1<<64
for i in range(n):
hash[i+1] = (hash[i] * 131 + ord(s[i]))%MOD
p[i+1] = (p[i] * 131) % MOD

def hash_value(l,r):
return (hash[r] - hash[l-1]*p[r-l+1])%MOD

for _ in range(m):
l1,r1,l2,r2 = map(int,input().split())

print("Yes" if hash_value(l1,r1) == hash_value(l2,r2) else "No")