68 lines
No EOL
1.5 KiB
Python
68 lines
No EOL
1.5 KiB
Python
import sys
|
|
|
|
data = sys.stdin.read().split()
|
|
if not data:
|
|
exit()
|
|
n = int(data[0])
|
|
m = int(data[1])
|
|
k = int(data[2])
|
|
a = [0] * (n + 1)
|
|
max_val = 0
|
|
for i in range(1, n + 1):
|
|
a[i] = int(data[2 + i])
|
|
if a[i] > max_val:
|
|
max_val = a[i]
|
|
adj = [[] for _ in range(n + 1)]
|
|
idx = 3 + n
|
|
for _ in range(m):
|
|
u = int(data[idx])
|
|
v = int(data[idx+1])
|
|
adj[u].append(v)
|
|
idx += 2
|
|
l = 1
|
|
r = max_val
|
|
ans = -1
|
|
while l <= r:
|
|
mid = (l + r) // 2
|
|
in_degree = [0] * (n + 1)
|
|
valid_count = 0
|
|
for u in range(1, n + 1):
|
|
if a[u] <= mid:
|
|
valid_count += 1
|
|
for v in adj[u]:
|
|
if a[v] <= mid:
|
|
in_degree[v] += 1
|
|
q = []
|
|
dp = [0] * (n + 1)
|
|
possible = False
|
|
for i in range(1, n + 1):
|
|
if a[i] <= mid:
|
|
dp[i] = 1
|
|
if dp[i] >= k:
|
|
possible = True
|
|
if in_degree[i] == 0:
|
|
q.append(i)
|
|
head = 0
|
|
visited_count = 0
|
|
while head < len(q) and not possible:
|
|
u = q[head]
|
|
head += 1
|
|
visited_count += 1
|
|
for v in adj[u]:
|
|
if a[v] <= mid:
|
|
if dp[u] + 1 > dp[v]:
|
|
dp[v] = dp[u] + 1
|
|
if dp[v] >= k:
|
|
possible = True
|
|
break
|
|
in_degree[v] -= 1
|
|
if in_degree[v] == 0:
|
|
q.append(v)
|
|
if visited_count < valid_count:
|
|
possible = True
|
|
if possible:
|
|
ans = mid
|
|
r = mid - 1
|
|
else:
|
|
l = mid + 1
|
|
print(ans) |