結果
| 問題 | No.3463 Beltway |
| コンテスト | |
| ユーザー |
 まぬお
|
| 提出日時 | 2026-02-28 16:01:27 |
| 言語 | PyPy3 (7.3.17) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 32,879 bytes |
| 記録 | |
| コンパイル時間 | 279 ms |
| コンパイル使用メモリ | 84,364 KB |
| 実行使用メモリ | 247,156 KB |
| 最終ジャッジ日時 | 2026-02-28 16:01:42 |
| 合計ジャッジ時間 | 13,291 ms |
|
ジャッジサーバーID （参考情報） |
judge7 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 5 WA * 4 RE * 7 TLE * 1 |
ソースコード
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, groupby
from heapq import heappop, heappush
import math, sys
input = lambda: sys.stdin.readline().rstrip("\r\n")
def printl(li, sep=" "): print(sep.join(map(str, li)))
def yn(flag): print(Yes if flag else No)
_int = lambda x: int(x)-1
MOD = 998244353 #10**9+7
INF = 1<<60
Yes, No = "Yes", "No"
def _ceil_pow2(n: int) -> int:
x = 0
while (1 << x) < n:
x += 1
return x
import typing
class LazySegTree:
def __init__(
self,
op: typing.Callable[[typing.Any, typing.Any], typing.Any],
e: typing.Any,
mapping: typing.Callable[[typing.Any, typing.Any], typing.Any],
composition: typing.Callable[[typing.Any, typing.Any], typing.Any],
id_: typing.Any,
v: typing.Union[int, typing.List[typing.Any]]) -> None:
self._op = op
self._e = e
self._mapping = mapping
self._composition = composition
self._id = id_
if isinstance(v, int):
v = [e] * v
self._n = len(v)
self._log = _ceil_pow2(self._n)
self._size = 1 << self._log
self._d = [e] * (2 * self._size)
self._lz = [self._id] * self._size
for i in range(self._n):
self._d[self._size + i] = v[i]
for i in range(self._size - 1, 0, -1):
self._update(i)
def set(self, p: int, x: typing.Any) -> None:
assert 0 <= p < self._n
p += self._size
for i in range(self._log, 0, -1):
self._push(p >> i)
self._d[p] = x
for i in range(1, self._log + 1):
self._update(p >> i)
def get(self, p: int) -> typing.Any:
assert 0 <= p < self._n
p += self._size
for i in range(self._log, 0, -1):
self._push(p >> i)
return self._d[p]
def prod(self, left: int, right: int) -> typing.Any:
assert 0 <= left <= right <= self._n
if left == right:
return self._e
left += self._size
right += self._size
for i in range(self._log, 0, -1):
if ((left >> i) << i) != left:
self._push(left >> i)
if ((right >> i) << i) != right:
self._push((right - 1) >> i)
sml = self._e
smr = self._e
while left < right:
if left & 1:
sml = self._op(sml, self._d[left])
left += 1
if right & 1:
right -= 1
smr = self._op(self._d[right], smr)
left >>= 1
right >>= 1
return self._op(sml, smr)
def all_prod(self) -> typing.Any:
return self._d[1]
def apply(self, left: int, right: typing.Optional[int] = None,
f: typing.Optional[typing.Any] = None) -> None:
assert f is not None
if right is None:
p = left
assert 0 <= left < self._n
p += self._size
for i in range(self._log, 0, -1):
self._push(p >> i)
self._d[p] = self._mapping(f, self._d[p])
for i in range(1, self._log + 1):
self._update(p >> i)
else:
assert 0 <= left <= right <= self._n
if left == right:
return
left += self._size
right += self._size
for i in range(self._log, 0, -1):
if ((left >> i) << i) != left:
self._push(left >> i)
if ((right >> i) << i) != right:
self._push((right - 1) >> i)
l2 = left
r2 = right
while left < right:
if left & 1:
self._all_apply(left, f)
left += 1
if right & 1:
right -= 1
self._all_apply(right, f)
left >>= 1
right >>= 1
left = l2
right = r2
for i in range(1, self._log + 1):
if ((left >> i) << i) != left:
self._update(left >> i)
if ((right >> i) << i) != right:
self._update((right - 1) >> i)
def max_right(
self, left: int, g: typing.Callable[[typing.Any], bool]) -> int:
assert 0 <= left <= self._n
assert g(self._e)
if left == self._n:
return self._n
left += self._size
for i in range(self._log, 0, -1):
self._push(left >> i)
sm = self._e
first = True
while first or (left & -left) != left:
first = False
while left % 2 == 0:
left >>= 1
if not g(self._op(sm, self._d[left])):
while left < self._size:
self._push(left)
left *= 2
if g(self._op(sm, self._d[left])):
sm = self._op(sm, self._d[left])
left += 1
return left - self._size
sm = self._op(sm, self._d[left])
left += 1
return self._n
def min_left(self, right: int, g: typing.Any) -> int:
assert 0 <= right <= self._n
assert g(self._e)
if right == 0:
return 0
right += self._size
for i in range(self._log, 0, -1):
self._push((right - 1) >> i)
sm = self._e
first = True
while first or (right & -right) != right:
first = False
right -= 1
while right > 1 and right % 2:
right >>= 1
if not g(self._op(self._d[right], sm)):
while right < self._size:
self._push(right)
right = 2 * right + 1
if g(self._op(self._d[right], sm)):
sm = self._op(self._d[right], sm)
right -= 1
return right + 1 - self._size
sm = self._op(self._d[right], sm)
return 0
def _update(self, k: int) -> None:
self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])
def _all_apply(self, k: int, f: typing.Any) -> None:
self._d[k] = self._mapping(f, self._d[k])
if k < self._size:
self._lz[k] = self._composition(f, self._lz[k])
def _push(self, k: int) -> None:
self._all_apply(2 * k, self._lz[k])
self._all_apply(2 * k + 1, self._lz[k])
self._lz[k] = self._id
class DSU:
'''
Implement (union by size) + (path halving)
Reference:
Zvi Galil and Giuseppe F. Italiano,
Data structures and algorithms for disjoint set union problems
'''
def __init__(self, n: int = 0) -> None:
self._n = n
self.parent_or_size = [-1] * n
def merge(self, a: int, b: int) -> int:
assert 0 <= a < self._n
assert 0 <= b < self._n
x = self.leader(a)
y = self.leader(b)
if x == y:
return x
if -self.parent_or_size[x] < -self.parent_or_size[y]:
x, y = y, x
self.parent_or_size[x] += self.parent_or_size[y]
self.parent_or_size[y] = x
return x
def same(self, a: int, b: int) -> bool:
assert 0 <= a < self._n
assert 0 <= b < self._n
return self.leader(a) == self.leader(b)
def leader(self, a: int) -> int:
assert 0 <= a < self._n
parent = self.parent_or_size[a]
while parent >= 0:
if self.parent_or_size[parent] < 0:
return parent
self.parent_or_size[a], a, parent = (
self.parent_or_size[parent],
self.parent_or_size[parent],
self.parent_or_size[self.parent_or_size[parent]]
)
return a
def size(self, a: int) -> int:
assert 0 <= a < self._n
return -self.parent_or_size[self.leader(a)]
def groups(self) -> typing.List[typing.List[int]]:
leader_buf = [self.leader(i) for i in range(self._n)]
result: typing.List[typing.List[int]] = [[] for _ in range(self._n)]
for i in range(self._n):
result[leader_buf[i]].append(i)
return list(filter(lambda r: r, result))
class HLD:
N: int
E: list[list[tuple[int, int]]]
root: int
parent: list[int]
depth: list[int]
size: list[int]
heavy: list[int]
head: list[int]
vid: list[int]
inv_vid: list[int]
dist_from_root: list[int]
edge_to_child: list[int]
def __init__(self, N: int, E, root: int = 0) -> None:
"""HLD (Heavy-Light Decomposition) クラスを初期化し、内部構造を構築する。
Args:
N (int): 木の頂点数。
E (Union[List[Tuple], List[List]]): 木の構造を表すデータ。
辺リスト形式 [(u, v), ...] もしくは [(u, v, w), ...]、
または隣接リスト形式 [[v, ...], ...] もしくは [[(v, w), ...], ...]。
root (int): 木の根とする頂点番号。デフォルトは 0。
Note:
Codonの静的型チェックを回避するため、辺リストの解析にはリスト変換を利用している。
"""
self.N = N
self.root = root
self.E = [[] for _ in range(N)]
self.edge_to_child = []
edge_list_for_child: list[tuple[int, int]] = []
if len(E) > 0:
sample = E[0]
if isinstance(sample, tuple):
for e in E:
e_list = list(e)
u, v = e_list[0], e_list[1]
w = e_list[2] if len(e_list) >= 3 else 1
self.E[u].append((v, w))
self.E[v].append((u, w))
edge_list_for_child.append((u, v))
else:
for i in range(N):
for e in E[i]:
if isinstance(e, int):
v_id = e
w_val = 1
else:
# タプルやリストから安全に値を取る
e_inner = list(e)
v_id = e_inner[0]
w_val = e_inner[1]
self.E[i].append((v_id, w_val))
if i < v_id:
edge_list_for_child.append((i, v_id))
self.parent = [0] * N
self.depth = [0] * N
self.size = [0] * N
self.heavy = [-1] * N
self.head = [0] * N
self.vid = [0] * N
self.inv_vid = []
self.dist_from_root = [0] * N
self._build()
if len(edge_list_for_child) > 0:
self.edge_to_child = [0] * len(edge_list_for_child)
for i in range(len(edge_list_for_child)):
uv = edge_list_for_child[i]
u_id, v_id = uv[0], uv[1]
self.edge_to_child[i] = v_id if self.depth[v_id] > self.depth[u_id] else u_id
def _build(self) -> None:
"""木の情報を走査し、部分木サイズ、重い辺、各頂点のHLD上のIDを計算する。
このメソッドは内部的に2回の走査を行う:
1. BFS/スタックによる走査で親子関係、深さ、根からの距離を計算。
2. 逆順走査で部分木サイズと重い子 (heavy child) を決定。
その後、重い辺を優先的に走査してパスを分解 (Heavy-Light Decomposition) し、
各頂点にセグメント木等で利用可能な連続した ID (vid) を割り当てる。
"""
N = self.N
E = self.E
parent = self.parent
depth = self.depth
size = self.size
dist_from_root = self.dist_from_root
heavy = self.heavy
q = [(-1, self.root)]
order = []
while q:
p, i = q.pop()
order.append(i)
parent[i] = p
size[i] = 1
for j, w in E[i]:
if p == j: continue
depth[j] = depth[i]+1
dist_from_root[j] = dist_from_root[i]+w
q.append((i, j))
for i in reversed(order):
p = parent[i]
if p == -1: continue
size[p] += size[i]
if heavy[p] == -1 or size[heavy[p]] < size[i]:
heavy[p] = i
head = self.head
vid = self.vid
inv_vid = self.inv_vid
q = [(self.root, self.root)]
while q:
i, hi = q.pop()
inv_vid.append(i)
head[i] = hi
for j, _ in E[i]:
if j == parent[i]: continue
if j == heavy[i]: continue
q.append((j, j))
if heavy[i] >= 0:
q.append((heavy[i], hi))
for i in range(N):
vid[inv_vid[i]] = i
def get_lca(self, u: int, v: int):
"""2頂点 u, v の最近共通祖先 (LCA) を返す。
Args:
u (int): 頂点番号。
v (int): 頂点番号。
Returns:
int: LCA となる頂点番号。
"""
head = self.head
depth = self.depth
parent = self.parent
while True:
hu = head[u]
hv = head[v]
if hu == hv: break
if depth[hu] < depth[hv]:
v = parent[hv]
else:
u = parent[hu]
lca = u if depth[u] < depth[v] else v
return lca
def kth_ancestor(self, u: int, k: int) -> int:
"""頂点 u から k 個上の祖先を返す。
Args:
u (int): 頂点番号。
k (int): 遡る数。
Returns:
int: 祖先の頂点番号。存在しない場合は -1。
"""
head = self.head
depth = self.depth
parent = self.parent
target = depth[u] - k
if target < 0: return -1
while True:
hu = head[u]
if depth[hu] <= target: break
u = parent[head[u]]
vid = self.vid
uid = vid[u]
targetid = uid - (depth[u]-target)
v = self.inv_vid[targetid]
return v
def jump(self, u: int, v: int, k: int) -> int:
"""u-v パス上で u から数えて k 個目の頂点を返す。
Args:
u (int): 始点。
v (int): 終点。
k (int): 移動ステップ数。
Returns:
int: 到達した頂点番号。パスの長さを超える場合は -1。
"""
d = self.get_edge_dist(u, v)
if k > d: return -1
lca = self.get_lca(u, v)
d_u = self.depth[u] - self.depth[lca]
if d_u >= k:
return self.kth_ancestor(u, k)
else:
return self.kth_ancestor(v, d - k)
def get_dist(self, u: int, v: int) -> int:
"""2頂点 u, v 間の最短距離（重みの総和）を返す。
Args:
u (int): 頂点1。
v (int): 頂点2。
Returns:
int: u-v 間の累積重み。
"""
lca = self.get_lca(u, v)
return self.dist_from_root[u] + self.dist_from_root[v] - 2 * self.dist_from_root[lca]
def is_on_path(self, u: int, v: int, x: int) -> bool:
"""頂点 x がパス u-v 上に存在するか判定する。
Args:
u (int): パス端点1。
v (int): パス端点2。
x (int): 判定対象の頂点。
Returns:
bool: x がパス上に存在すれば True。
"""
return self.get_edge_dist(u, x) + self.get_edge_dist(x, v) == self.get_edge_dist(u, v)
def get_edge_dist(self, u: int, v: int) -> int:
"""2頂点間のエッジ数(重みによらない距離)を計算する。
Args:
u (int): 頂点1。
v (int): 頂点2。
Returns:
int: u-v パスを構成するエッジの個数。
"""
lca = self.get_lca(u, v)
return self.depth[u] + self.depth[v] - 2 * self.depth[lca]
def path_sections(self, u: int, v: int, edge: bool = False):
"""
u-v パスをセグメント木上の連続区間 [l, r) に分解して yield する。
戻り値: (l, r, is_reverse)
Args:
u, v: 端点となる頂点
edge: True の場合、辺クエリ(LCAを含まない)として処理する
"""
head = self.head
depth = self.depth
parent = self.parent
vid = self.vid
# u側（登り）とv側（最終的に降りになる）の区間を溜めるリスト
# 各要素は (l, r, is_reverse)
l_parts: list[tuple[int, int, bool]] = []
r_parts: list[tuple[int, int, bool]] = []
while head[u] != head[v]:
if depth[head[u]] > depth[head[v]]:
# u側を登る: IDが減る方向なので is_reverse=True
l_parts.append((vid[head[u]], vid[u] + 1, True))
u = parent[head[u]]
else:
# v側を登る: 後で逆順(降り)にするため、ここでは反転させない(False)
r_parts.append((vid[head[v]], vid[v] + 1, False))
v = parent[head[v]]
# 同じ Chain に到達した後の、LCA付近の処理
if depth[u] > depth[v]:
# u側が深い場合
l_offset = 1 if edge else 0
# 頂点クエリなら [vid[v], vid[u]+1], 辺クエリなら [vid[v]+1, vid[u]+1]
if vid[v] + l_offset < vid[u] + 1:
l_parts.append((vid[v] + l_offset, vid[u] + 1, True))
else:
# v側が深い(または同じ)場合
r_offset = 1 if edge else 0
# 頂点クエリなら [vid[u], vid[v]+1], 辺クエリなら [vid[u]+1, vid[v]+1]
if vid[u] + r_offset < vid[v] + 1:
r_parts.append((vid[u] + r_offset, vid[v] + 1, False))
# 1. u から LCA への昇順区間を順番に出す
for section in l_parts:
yield section
# 2. v 側のリストを逆順にして、LCA から v へ降りる順序で出す
# reversed() を使うことで、LCAに近い方の区間から順に出現する
for section in reversed(r_parts):
yield section
def prod_path(self, u: int, v: int, e, prod_func, op, edge: bool = False):
"""u-v パス上の値を集約して返す。
Args:
u (int): 始点。
v (int): 終点。
e (T): 単位元。
prod_func (Callable[[int, int], tuple[T, T]]): セグメント木の範囲取得関数。 (forward, backward) のペアを返す必要があります。
op (Callable[[T, T], T]): 二項演算。
edge (bool): True の場合、辺クエリ (LCA を含まない) として処理する。
Returns:
T: パス上の要素を op で集約した結果。
"""
res = e
for l, r, is_rev in self.path_sections(u, v, edge):
fwd, bwd = prod_func(l, r)
# 登りなら backward、降りなら forward を使う
chunk = bwd if is_rev else fwd
res = op(res, chunk)
return res
def prod_subtree(self, u: int, e, prod_func, op, edge: bool = False):
"""頂点 u の部分木を集約して返す。
Args:
u (int): 部分木の根となる頂点。
e (T): 単位元。
prod_func (Callable[[int, int], tuple[T, T]]): セグメント木の範囲取得関数。
op (Callable[[T, T], T]): 二項演算。
edge (bool): True の場合、辺クエリ (u 直上の辺を含まない) として処理する。
Returns:
T: 部分木内の要素を集約した結果。
"""
l = self.vid[u]
r = self.vid[u] + self.size[u]
if edge:
l += 1
if l < r:
fwd, _ = prod_func(l, r)
return fwd
return e
def apply_path(self, u: int, v: int, x, apply_func, edge: bool = False) -> None:
"""u-v パス上の要素に一括操作 (範囲更新) を適用する。
Args:
u (int): 始点。
v (int): 終点。
x (F): 作用させる値 (作用素)。
apply_func (Callable[[int, int, F], None]): セグメント木の範囲更新関数 (apply(l, r, x))。
edge (bool): True の場合、辺クエリ (LCA を含まない) として処理する。
"""
for l, r, _ in self.path_sections(u, v, edge):
apply_func(l, r, x)
def apply_subtree(self, u: int, x, apply_func, edge: bool = False) -> None:
"""頂点 u の部分木に一括操作 (範囲更新) を適用する。
Args:
u (int): 部分木の根となる頂点。
x (F): 作用させる値 (作用素)。
apply_func (Callable[[int, int, F], None]): セグメント木の範囲更新関数 (apply(l, r, x))。
edge (bool): True の場合、辺クエリ (u 直上の辺を含まない) として処理する。
"""
l = self.vid[u]
r = self.vid[u] + self.size[u]
if edge:
l += 1
if l < r:
apply_func(l, r, x)
def set(self, u: int, set_func, x) -> None:
"""頂点 u の値を更新する。
Args:
u (int): 更新対象の頂点。
set_func (Callable[[int, tuple[T, T]], None]): セグメント木の一点更新関数。
x (T): 更新後の値。
"""
set_func(self.vid[u], (x, x))
def set_edge_by_id(self, edge_id: int, set_func, x) -> None:
"""入力時の辺 ID を指定して、辺の重みを更新する。
Args:
edge_id (int): E に与えられた辺のインデックス。
set_func (Callable[[int, tuple[T, T]], None]): セグメント木の一点更新関数。
x (T): 更新後の重み。
"""
child = self.edge_to_child[edge_id]
set_func(self.vid[child], (x, x))
def get(self, u: int, get_func):
"""頂点 u の現在の値を取得する。
Args:
u (int): 取得対象の頂点。
get_func (Callable[[int], tuple[T, T]]): セグメント木の一点取得関数。
Returns:
T: 頂点 u の現在の値。
"""
val_pair = get_func(self.vid[u])
return val_pair[0]
def get_edge_by_id(self, edge_id: int, get_func):
"""入力時の辺 ID を指定して、辺の現在の重みを取得する。
Args:
edge_id (int): E に与えられた辺のインデックス。
get_func (Callable[[int], tuple[T, T]]): セグメント木の一点取得関数。
Returns:
T: 指定された辺の現在の重み。
"""
child = self.edge_to_child[edge_id]
val_pair = get_func(self.vid[child])
return val_pair[0]
def make_v(self, original_values: list, e, edge: bool = False):
"""元の順序の値を、HLD順に並べ替えた (forward, backward) のペアリストに変換する。
セグメント木の初期化用データを作成する際に使用します。
Args:
original_values (list): 元の順序の値リスト。
頂点クエリの場合は頂点 0, 1, ..., N-1 の値 (長さ N)。
辺クエリの場合は入力された辺 0, 1, ..., M-1 の値 (長さ N-1)。
e (T): 単位元。辺クエリで根に対応する位置を埋めるために使用。
edge (bool): 辺重みのリストを作成する場合は True。
Returns:
list[tuple[T, T]]: セグ木構築用の (val, val) のリスト。
"""
if not edge:
# 頂点クエリの場合、頂点数とリストの長さが一致することを確認
assert len(original_values) == self.N, f"Expected length {self.N}, but got {len(original_values)}"
hld_ordered: list = [original_values[0]] * self.N # 型推論のための仮初期化
for i, val in enumerate(original_values):
hld_ordered[self.vid[i]] = val
else:
# 辺クエリの場合、根の補完用 e が必須であり、リストの長さは N-1 であることを確認
if e is None: # assertの代わりに明示的なif
raise ValueError("Edge queries require identity element e")
assert len(original_values) == self.N - 1, f"Expected length {self.N-1}, but got {len(original_values)}"
hld_ordered = [e] * self.N
for i, val in enumerate(original_values):
child = self.edge_to_child[i]
hld_ordered[self.vid[child]] = val
return [(x, x) for x in hld_ordered]
@staticmethod
def make_op(op):
"""非可換演算を (forward, backward) のペアで扱えるようにラップする。
セグメント木の初期化時に渡す演算関数を作成します。
forward は左から右 (a -> b)、backward は右から左 (b -> a) の順で演算を適用します。
Args:
op (Callable[[T, T], T]): 元の二項演算 (例: 行列の積、文字列の結合など)。
Returns:
Callable[[tuple[T, T], tuple[T, T]], tuple[T, T]]:
ペアを受け取りペアを返す、セグメント木用の二項演算関数。
"""
return lambda a, b: (op(a[0], b[0]), op(b[1], a[1]))
@staticmethod
def make_e(e):
"""単位元を (forward, backward) のペアにする。
セグメント木の初期化時に渡す単位元を作成します。
Args:
e (T): 元の演算における単位元。
Returns:
tuple[T, T]: (e, e) のペア。
"""
return (e, e)
@staticmethod
def make_mapp(mapp):
"""作用関数を (forward, backward) ペア用にラップします。
HLDで非可換なパスを扱う際、セグメント木のデータ S が (fwd, bwd) のペアになるため、
単一の作用素 f を両方の要素に適用するように変換します。
Args:
mapp (Callable[[F, T], T]): 元の作用関数。
第1引数に作用素 (F)、第2引数にデータ (T) を受け取り、新しいデータを返すもの。
Returns:
Callable[[F, Tuple[T, T]], Tuple[T, T]]: ラップされた作用関数。
"""
return lambda f, x: (mapp(f, x[0]), mapp(f, x[1]))
@staticmethod
def make_comp(comp):
"""作用素の合成関数を、インターフェースの対称性のためにラップします。
作用素 F は HLD によるペア化の影響を受けないため、基本的には引数をそのまま返します。
Args:
comp (Callable[[F, F], F]): 元の合成関数。
第1引数に新しい作用素、第2引数に古い作用素を受け取り、合成された作用素を返すもの。
Returns:
Callable[[F, F], F]: 入力された合成関数をそのまま返します。
"""
return comp
@staticmethod
def make_id(id):
"""作用素の単位元を、インターフェースの対称性のためにラップします。
データ S と異なり、作用素 F はペア化されないため、値は変更されません。
Args:
f (F): 元の作用素の単位元 (identity element)。
Returns:
F: 入力された単位元をそのまま返します。
"""
return id
# -----------------------------------------------------------------
# HLD 使用例 (Usage Examples)
# -----------------------------------------------------------------
"""
1. 準備: セグメント木 (一点更新・パス集約)
例: パス上の行列積や最大値など (非可換対応)
"""
# def op(a, b): return a+b
# e = 0
# S = SegTree(
# hld.make_op(op),
# hld.make_e(e),
# hld.make_v(v, e)
# )
"""
2. 準備: 遅延セグメント木 (範囲更新・パス更新)
例: パス一括加算、パス一括塗りつぶし
"""
# def op(a, b): return a+b
# e = 0
# def mapp(f, x): return f+x
# def comp(f, g): return f+g
# id = 0
# S = LazySegTree(
# hld.make_op(op),
# hld.make_e(e),
# hld.make_mapp(mapp),
# hld.make_comp(comp),
# hld.make_id(id),
# hld.make_v(v, e)
# )
"""
3. 頂点クエリ (Vertex Queries)
"""
# --- 値の更新 (一点) ---
# hld.set(u, S.set, x)
# --- パス集約 (u から v への順序を考慮) ---
# res = hld.prod_path(u, v, e, S.prod, op)
# --- 部分木集約 ---
# res = hld.prod_subtree(u, e, S.prod, op)
# --- パス一括更新 (遅延セグ木使用) ---
# hld.apply_path(u, v, x, S.apply)
# --- 部分木一括更新 (遅延セグ木使用) ---
# hld.apply_subtree(u, x, S.apply)
"""
4. 辺クエリ (Edge Queries)
辺の値を「根から遠い方の頂点」に持たせて管理します。
edge=True を指定することで LCA (頂点) を自動的に除外します。
"""
# --- 準備 (辺の初期値リストから HLD 順のペアリストを作成) ---
# S = SegTree(
# hld.make_op(op),
# hld.make_e(e),
# hld.make_v(edge_weights, e, edge=True)
# )
# --- 辺の値の更新 (入力時の i 番目の辺を指定) ---
# hld.set_edge_by_id(i, S.set, new_w)
# --- パス上の辺の集約 ---
# res = hld.prod_path(u, v, e, S.prod, op, edge=True)
# --- 頂点 u の直下にある部分木内の辺をすべて更新 ---
# hld.apply_subtree(u, x, S.apply, edge=True)
"""
5. その他便利機能 (Tree Metrics)
"""
# --- LCA (最近共通祖先) ---
# lca = hld.get_lca(u, v)
# --- 距離 (重みなしエッジ数 / 重みあり距離) ---
# 辺に重みがない場合は同じ結果になる。
# dist_steps = hld.get_edge_dist(u, v)
# dist_weighted = hld.get_dist(u, v)
# --- K個上の祖先 (存在しなければ -1) ---
# anc = hld.kth_ancestor(u, k)
# --- パス上のジャンプ (u から v 方向へ k ステップ移動) ---
# target = hld.jump(u, v, k)
def ctypes(li, types):
assert len(li) == len(types)
return [t(a) for a, t in zip(li, types)]
def tinput(*types):
li = input().split()
return ctypes(li, types)
def qinput(*types):
li = input().split()
t = int(li[0])
if len(li) == 1: return t, types[t-1][0](li[1])
else: return t, ctypes(li[1:], types[t-1])
N, M, si, ti = tinput(int, int, _int, _int)
FID = DSU(N)
UV = []
for _ in range(M):
u, v = tinput(_int, _int)
FID.merge(u, v)
UV.append((u, v))
if not FID.same(si, ti):
print(-1)
V = []
for i in range(N):
if not FID.same(si, i): continue
V.append(i)
N = len(V)
pos = {x: e for e, x in enumerate(V)}
E = [[] for _ in range(N)]
edges = []
D = DSU(N)
for u, v in UV:
if not FID.same(si, u): continue
u, v = pos[u], pos[v]
if u > v: u, v = v, u
if D.same(u, v): continue
D.merge(u, v)
edges.append((u, v))
hld = HLD(N, edges, 0)
def op(a, b): return a+b
e = 0
def mapp(f, x): return f+x
def comp(f, g): return f+g
id = 0
S = LazySegTree(
hld.make_op(op),
hld.make_e(e),
hld.make_mapp(mapp),
hld.make_comp(comp),
hld.make_id(id),
hld.make_v([0]*N, e)
)
E = [[] for _ in range(N)]
D = DSU(N)
eset = set()
for u, v in UV:
if not FID.same(si, u): continue
u, v = pos[u], pos[v]
if u > v: u, v = v, u
E[u].append(v)
E[v].append(u)
if D.same(u, v):
eset.add((u, v))
hld.apply_path(u, v, 1, S.apply)
D.merge(u, v)
for e, (u, v) in enumerate(edges):
if S.get(e)[0] > 0:
eset.add((u, v))
si = pos[si]
ti = pos[ti]
q = deque([si])
dist = [0]*N
vis = [0]*N
vis[si] = 0
dist[si] = 0
while q:
i = q.popleft()
vis[i] = 2
for j in E[i]:
if vis[j] == 2: continue
if i > j:
loop = 1 if (j, i) in eset else 0
else:
loop = 1 if (i, j) in eset else 0
if dist[j] < dist[i]+loop:
dist[j] = dist[i]+loop
if vis[j]: continue
vis[j] = 1
q.append(j)
print(dist[ti])