Berland has n cities, the capital is located in city s, and the historic home town of the President is in city t (s ≠ t). The cities are connected by one-way roads, the travel time for each of the road is a positive integer.

Once a year the President visited his historic home town t, for which his motorcade passes along some path from s to t (he always returns on a personal plane). Since the president is a very busy man, he always chooses the path from s to t, along which he will travel the fastest.

The ministry of Roads and Railways wants to learn for each of the road: whether the President will definitely pass through it during his travels, and if not, whether it is possible to repair it so that it would definitely be included in the shortest path from the capital to the historic home town of the President. Obviously, the road can not be repaired so that the travel time on it was less than one. The ministry of Berland, like any other, is interested in maintaining the budget, so it wants to know the minimum cost of repairing the road. Also, it is very fond of accuracy, so it repairs the roads so that the travel time on them is always a positive integer.


-----Input-----

The first lines contain four integers n, m, s and t (2 ≤ n ≤ 10^5; 1 ≤ m ≤ 10^5; 1 ≤ s, t ≤ n) — the number of cities and roads in Berland, the numbers of the capital and of the Presidents' home town (s ≠ t).

Next m lines contain the roads. Each road is given as a group of three integers a_{i}, b_{i}, l_{i} (1 ≤ a_{i}, b_{i} ≤ n; a_{i} ≠ b_{i}; 1 ≤ l_{i} ≤ 10^6) — the cities that are connected by the i-th road and the time needed to ride along it. The road is directed from city a_{i} to city b_{i}.

The cities are numbered from 1 to n. Each pair of cities can have multiple roads between them. It is guaranteed that there is a path from s to t along the roads.


-----Output-----

Print m lines. The i-th line should contain information about the i-th road (the roads are numbered in the order of appearance in the input).

If the president will definitely ride along it during his travels, the line must contain a single word "YES" (without the quotes).

Otherwise, if the i-th road can be repaired so that the travel time on it remains positive and then president will definitely ride along it, print space-separated word "CAN" (without the quotes), and the minimum cost of repairing.

If we can't make the road be such that president will definitely ride along it, print "NO" (without the quotes).


-----Examples-----
Input
6 7 1 6
1 2 2
1 3 10
2 3 7
2 4 8
3 5 3
4 5 2
5 6 1

Output
YES
CAN 2
CAN 1
CAN 1
CAN 1
CAN 1
YES

Input
3 3 1 3
1 2 10
2 3 10
1 3 100

Output
YES
YES
CAN 81

Input
2 2 1 2
1 2 1
1 2 2

Output
YES
NO



-----Note-----

The cost of repairing the road is the difference between the time needed to ride along it before and after the repairing.

In the first sample president initially may choose one of the two following ways for a ride: 1 → 2 → 4 → 5 → 6 or 1 → 2 → 3 → 5 → 6.

Difficulty: HARD
Tags: String algorithms

Graph algorithms

Graph traversal

Shortest paths

Starter code:

Solutions:
import heapq
INF = int(1e+18)
MOD = (1 << 64) - 1

class MinHeap:

	def __init__(self):
		self.h = []

	def push(self, x):
		heapq.heappush(self.h, x)

	def pop(self):
		return heapq.heappop(self.h)

	def isEmpty(self):
		return len(self.h) == 0

def add(x, y):
	return x + y - MOD if x + y >= MOD else x + y

def mul(x, y):
	return x * y % MOD

def go(adj, src):
	n = len(adj)
	frontier = MinHeap()
	ways = [0] * n
	cost = [INF] * n
	frontier.push((0, src))
	ways[src] = 1
	cost[src] = 0
	while not frontier.isEmpty():
		(c, u) = frontier.pop()
		if c > cost[u]:
			continue
		for (v, w) in adj[u]:
			if c + w < cost[v]:
				ways[v] = ways[u]
				cost[v] = c + w
				frontier.push((c + w, v))
			elif c + w == cost[v]:
				ways[v] = add(ways[v], ways[u])
	return (cost, ways)
(n, m, s, t) = map(int, input().split())
s -= 1
t -= 1
adj = [[] for i in range(n)]
adj_transpose = [[] for i in range(n)]
edges = []
for i in range(m):
	(u, v, w) = map(int, input().split())
	u -= 1
	v -= 1
	edges.append((u, v, w))
	adj[u].append((v, w))
	adj_transpose[v].append((u, w))
(cost_s, ways_s) = go(adj, s)
(cost_t, ways_t) = go(adj_transpose, t)
shortest_path = cost_s[t]
for i in range(m):
	(u, v, w) = edges[i]
	cost = cost_s[u] + cost_t[v] + w
	if cost > shortest_path:
		fix_cost = cost - shortest_path + 1
		w -= cost - shortest_path + 1
		print(f'CAN {fix_cost}' if w >= 1 else 'NO')
	elif ways_s[t] == mul(ways_s[u], ways_t[v]):
		print('YES')
	else:
		print('CAN 1' if w > 1 else 'NO')


from heapq import *
from collections import defaultdict

def D(v, g):
	(h, p, o) = ([], defaultdict(lambda : 1e+99), [])
	heappush(h, (0, v))
	while h:
		(l, w) = heappop(h)
		if w in p:
			continue
		p[w] = l
		o.append(w)
		for (u, L) in g[w]:
			heappush(h, (L + l, u))
	return (p, o)
(n, m, s, t) = list(map(int, input().split()))
r = []
g = {i + 1: [] for i in range(n)}
G = {i + 1: [] for i in range(n)}
for _ in range(m):
	(a, b, l) = list(map(int, input().split()))
	r.append((a, b, l))
	g[a].append((b, l))
	G[b].append((a, l))
(S, o) = D(s, g)
(T, _) = D(t, G)
L = S[t]
H = {v: [w for (w, l) in e if S[v] + T[w] + l == L] for (v, e) in list(g.items())}
(B, A) = (set(), {s})
for v in o:
	if not H[v]:
		continue
	if 1 == len(A) == len(H[v]):
		B.add(v)
	A.update(H[v])
	A.remove(v)
print('\n'.join(('YES' if a in B and S[a] + T[b] + l == L else 'CAN ' + str(S[a] + T[b] + l - L + 1) if S[a] + T[b] + 1 < L else 'NO' for (a, b, l) in r)))


from heapq import *
import sys
MOD = 1000000181

def addM(a, b):
	return (a + b) % MOD

def mulM(a, b):
	return a * b % MOD

def dijk(adj, n, s):
	dist = [10 ** 18] * n
	ways = [0] * n
	frontier = []
	dist[s] = 0
	ways[s] = 1
	heappush(frontier, (0, s))
	while len(frontier) > 0:
		x = heappop(frontier)
		if x[0] != dist[x[1]]:
			continue
		x = x[1]
		for (i, l) in adj[x]:
			if dist[x] + l < dist[i]:
				dist[i] = dist[x] + l
				ways[i] = ways[x]
				heappush(frontier, (dist[i], i))
			elif dist[x] + l == dist[i]:
				ways[i] = addM(ways[i], ways[x])
	return (dist, ways)
(n, m, s, t) = map(int, sys.stdin.readline().split())
s -= 1
t -= 1
adj = [[] for i in range(n)]
jda = [[] for i in range(n)]
edges = []
for i in range(m):
	(a, b, l) = map(int, sys.stdin.readline().split())
	a -= 1
	b -= 1
	adj[a].append((b, l))
	jda[b].append((a, l))
	edges.append((a, b, l))
one = dijk(adj, n, s)
two = dijk(jda, n, t)
for i in edges:
	if one[0][i[0]] + i[2] + two[0][i[1]] == one[0][t] and mulM(one[1][i[0]], two[1][i[1]]) == one[1][t]:
		sys.stdout.write('YES\n')
	else:
		x = one[0][t] - 1 - one[0][i[0]] - two[0][i[1]]
		if x <= 0:
			sys.stdout.write('NO\n')
		else:
			sys.stdout.write('CAN ' + str(i[2] - x) + '\n')


import heapq

def dijkstra(a, graph):
	shortestPaths = [None] * len(graph)
	priorityQueue = []
	heapq.heappush(priorityQueue, (0, a))
	while len(priorityQueue) != 0:
		(length, endpoint) = heapq.heappop(priorityQueue)
		if shortestPaths[endpoint] != None:
			continue
		shortestPaths[endpoint] = length
		for (b, l, i) in graph[endpoint]:
			if shortestPaths[b] != None:
				continue
			heapq.heappush(priorityQueue, (length + l, b))
	return shortestPaths
(n, m, s, t) = map(int, input().split())
s -= 1
t -= 1
roads = []
graph = [[] for _ in range(n)]
backwardsGraph = [[] for _ in range(n)]
for i in range(m):
	(a, b, l) = map(int, input().split())
	a -= 1
	b -= 1
	roads.append((a, b, l, i))
	graph[a].append((b, l, i))
	backwardsGraph[b].append((a, l, i))
leftDijkstras = dijkstra(s, graph)
rightDijkstras = dijkstra(t, backwardsGraph)
answers = [None] * m
events = []
for road in roads:
	(a, b, l, i) = road
	if leftDijkstras[a] == None or rightDijkstras[b] == None:
		continue
	pathTime = leftDijkstras[a] + rightDijkstras[b] + l
	if pathTime == leftDijkstras[t]:
		events.append((leftDijkstras[a], True, i))
		events.append((leftDijkstras[b], False, i))
events.sort()
edgeSet = set()
niceEdges = [True] * m
for event in events:
	if event[1] == True:
		edgeSet.add(event[2])
		if len(edgeSet) > 1:
			niceEdges[event[2]] = False
	else:
		edgeSet.remove(event[2])
		if len(edgeSet) != 0:
			niceEdges[event[2]] = False
for road in roads:
	(a, b, l, i) = road
	if leftDijkstras[a] == None or rightDijkstras[b] == None:
		answers[i] = 'NO'
		continue
	pathTime = leftDijkstras[a] + rightDijkstras[b] + l
	if pathTime == leftDijkstras[t] and niceEdges[i]:
		answers[i] = 'YES'
	else:
		difference = pathTime - leftDijkstras[t]
		if l > difference + 1:
			answers[i] = 'CAN ' + str(difference + 1)
		else:
			answers[i] = 'NO'
for i in range(len(answers)):
	print(answers[i])