Problem:


Score : 300 points

Problem Statement

You are given a string s.
Among the different substrings of s, print the K-th lexicographically smallest one.

A substring of s is a string obtained by taking out a non-empty contiguous part in s.
For example, if s = ababc, a, bab and ababc are substrings of s, while ac, z and an empty string are not.
Also, we say that substrings are different when they are different as strings.

Let X = x_{1}x_{2}...x_{n} and Y = y_{1}y_{2}...y_{m} be two distinct strings. X is lexicographically larger than Y if and only if Y is a prefix of X or x_{j} > y_{j} where j is the smallest integer such that x_{j} \neq y_{j}.

Constraints

1 ≤ |s| ≤ 5000

s consists of lowercase English letters.

1 ≤ K ≤ 5

s has at least K different substrings.

Partial Score

200 points will be awarded as a partial score for passing the test set satisfying |s| ≤ 50.

Input

Input is given from Standard Input in the following format:

s
K

Output

Print the K-th lexicographically smallest substring of K.

Sample Input 1

aba
4

Sample Output 1

b

s has five substrings: a, b, ab, ba and aba.
Among them, we should print the fourth smallest one, b.
Note that we do not count a twice.

Sample Input 2

atcoderandatcodeer
5

Sample Output 2

andat

Sample Input 3

z
1

Sample Output 3

z



Sample input:
aba
4


Sample output:
b

Submission status: Runtime Error

Solution code:
import bisect
 
s = input()
n = int(input())
 
dic = set()
a = []
 
for i in range(1, len(s)):
  for j in range(len(s) - i):
    sub = s[j:j + i]
    if sub in dic:
      continue
    dic.add(sub)
    bisect.insort(a, sub)
 
print(a[n - 1])

Submission status: Runtime Error

Solution code:
import bisect

s = input()
n = int(input())

dic = set()
a = []

for i in range(1, len(s)):
  for j in range(len(s) - i):
    sub = s[j:j + i]
    if sub in dic:
      continue
    d.add(sub)
    bisect.insort(a, sub)

print(a[n - 1])

Submission status: Runtime Error

Solution code:
s = input()
K = int(input())
n1 = list(s)
n2 = [s[i:i+2] for i in range(len(s)-1)]
n3 = [s[i:i+3] for i in range(len(s)-2)]
cat = list(set(n1 + n2 + n3))
cat.sort()
#print(cat)
print(cat[K-1])

Submission status: Runtime Error

Solution code:
s = str(input())
k = int(input())
result = []
for i in range(1, k+1):
    for j in range(len(s)-i):
        result.append(s[j:j+i])
r = set(result)
out = list(r)
out.sort()
print(out[k-1])

Submission status: Runtime Error

Solution code:
class uf():
    def __init__(self,n):
        self.root = [-1] * (n+1)

    def findroot(self,x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.findroot(self.root[x])
            return self.root[x]

    def unite(self,x,y):
        rootx = self.findroot(x)
        rooty = self.findroot(y)
        if rootx == rooty:
            return
        else:
            self.root[rootx] += self.root[rooty]
            self.root[rooty] = rootx
            return

    def is_same_group(self,x,y):
        return self.findroot(x) == self.findroot(y)

N,M = map(int, input().split())
P = list(map(int, input().split()))

uf = uf(N)

for _ in range(1,M+1):
    x,y = map(int, input().split())
    uf.unite(x,y)

count = 0
for n in range(N):
    if uf.is_same_group(P[n],n+1):
        count += 1

print(count)

Submission status: Runtime Error

Solution code:
import collections
s = input()
K = int(input())

abc = collections.defaultdict(list)

for i in range(len(s)):
  for j in range(1,K+1):
    if i+j < len(s):
        abc[s[i:i+j]].append(i)


abc = list(abc.items())
abc.sort(key=lambda x: x[0])


print(abc[K][0])

Submission status: Runtime Error

Solution code:
s=input()
n=int(input())
lst=[]
for i in range(len(s)):
  for j in range(i+1,min(i+n+1,len(s)+1)):
    lst.append(s[i:j])
sub=set(lst)
sub.sort()
print(sub[n-1])

Submission status: Runtime Error

Solution code:
from collections import deque
s=input()
length=len(s)

K=int(input())
#print(s,K)

left=0
right=0
#ss=s[left:right]
#print(ss)

ss=deque()
for left in range(length+1):
    for right in range(left+1,length+1):
      if right-left+1 <= K:
        ss.append(s[left:right])

myset=set(ss)
for i in range(K):
    tmp=min(myset)
    myset.remove(tmp)
print(tmp)

Submission status: Runtime Error

Solution code:
from collections import deque
s=input()
length=len(s)

K=int(input())
#print(s,K)

left=0
right=0
#ss=s[left:right]
#print(ss)

ss=deque()
for left in range(length+1):
    for right in range(left+1,length+1):
        ss.append(s[left:right])

myset=set(ss)
for i in range(k):
    tmp=min(myset)
    myset.remove(tmp)
print(tmp)

Submission status: Runtime Error

Solution code:
s=input()
k=int(input())
n=len(s)
li=[]
for i in range(min(n,k)):
  for j in range(n-i):
    li.append(s[j:j+i+1])
li.sort()
print(li[k])

Submission status: Runtime Error

Solution code:
S = list(input())
K = int(input())
x = set()

for i in range(len(S)):
    for j in range(1,min(len(S) - i + 1, K + 1)):
        x.add(S[i:i + j])

x = list(x)
x.sort()
print(x[K - 1])

Submission status: Runtime Error

Solution code:
s=input()
k=int(input())
c=[]
for i in range(len(s)):
    for j in range(min(len(s)-i,k)):
        t=s[i:i+j+1]
        if t not in cnt:
            c.append(t)
print(sorted(c)[k-1])

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
p = list(map(int,input().split()))
d = [list() for _ in range(n+1)]
cnt = 0
for _ in range(m):
  x,y = map(int, input().split())
  d[x].append(y)
  d[y].append(x)
gr = [0]*(n+1)
gr[0] = -1
gn = 0
for x in range(1,n+1):
  if gr[x] == 0:
    gn += 1
    gr[x] = gn
    l = [x]
    while l:
      cur = l.pop()
      for i in d[cur]:
        if i not in l and gr[i] == 0:
          gr[i] = gn
          l.append(i)
for i in range(n):
  if gr[i+1] == gr[p[i]]:
    cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
s = str(input())
K = int(input())

def find(str):
	lt = []
	for start in range(len(str)):
		for end in range(start + 1, len(str) + 1):
			lt.append(str[start:end])
	lt = list(set(lt))
	lt.sort()

	return lt

s_pt = list(set(list(s)))
s_pt.sort()
ans = []

for i in range(min(5, len(s_pt))):
	ind = [ix for ix, x in enumerate(s) if x == s_pt[i]]
	for j in ind:
		ans += find(s[j:min(j+5, len(s))])
	if len(ans) >= 5:
		break
ans = list(set(ans))
ans.sort()
print(ans[K-1])

Submission status: Runtime Error

Solution code:
s = str(input())
K = int(input())

def find(str):
	lt = []
	for start in range(len(str)):
		for end in range(start + 1, len(str) + 1):
			lt.append(str[start:end])
	lt = list(set(lt))
	lt.sort()

	return lt

s_pt = list(set(list(s)))
s_pt.sort()
ans = []

for i in range(5):
	ind = [ix for ix, x in enumerate(s) if x == s_pt[i]]
	for j in ind:
		ans += find(s[j:min(j+5, len(s))])
	if len(ans) >= 5:
		break
ans = list(set(ans))
ans.sort()
print(ans[K-1])

Submission status: Runtime Error

Solution code:
s = input()

K = int(input())

if len(s) == 1:
  print(s)
  exit()

else:
  w = []
  for a in range(len(s)-1):
    for b in range(1,len(s)+1):
      if s[a:b] != "":
        w.append(s[a:b])

z = sorted(set(w))      
print(z[K-1])

Submission status: Runtime Error

Solution code:
s = input()
K = int(input())
head = [h for h in s]

head = set(head)
head = list(head)
head.sort()

cnt = 0
ans = []
idx = 0
while cnt < K:
    for i in range(len(s)):
        if s[i] == head[idx]:
            for k in range(i+1, len(s)+1):
                ans.append(s[i:k])
                cnt += 1
    idx += 1
ans = set(ans)
ans = list(ans)
ans.sort()
print(ans[K-1])

Submission status: Runtime Error

Solution code:
s = input()
K = int(input())
head = [h for h in s]

head = set(head)
head = list(head)
head.sort()

cnt = 0
ans = []
idx = 0
while cnt <= K:
    for i in range(len(s)):
        if s[i] == head[idx]:
            for k in range(i+1, len(s)+1):
                ans.append(s[i:k])
                cnt += 1
    idx += 1
ans = set(ans)
ans = list(ans)
ans.sort()
print(ans[K-1])

Submission status: Runtime Error

Solution code:
s = input()
K = int(input())
ans = []
for i in range(len(s)):
    for k in range(i+1, len(s)):
        ans.append(s[i:k])
ans = set(ans)
ans = list(ans)
ans.sort()
print(ans[K-1])

Submission status: Runtime Error

Solution code:
s = input()
K = int(input())

sub = []
for i in range(1, len(s)+1):
    for k in range(len(s)-i+1):
        sub.append(s[k:k+i])

sub = list(set(sub))
sub.sort()
print(sub[k+1])

Submission status: Runtime Error

Solution code:
s=input()
k=int(input())
l=[]
for i in range(len(s)-1):
  for j in range(i+1,min(len(s),i+5)):
    if s[i:j] not in l:
      l.append(s[i:j])
l.sort()
print(l[k-1])

Submission status: Runtime Error

Solution code:
s = input()
K = int(input())

ct = 0
alp = 'abcdefghijklmnopqrstuvwxyz'
for i in alp:
    ct += s.count(i)
    if ct >= K:
        key = i
        break

list_rank = []
for i in range(len(s)):
    if s[i] > key:
        continue
    if i < len(s) - K + 1:
        for j in range(K):
            if s[i:i+j+1] not in list_rank:
                list_rank.append(s[i:i+j+1])
    else:
        for j in range(len(s)-i):
            if s[i:i+j+1] not in list_rank:
                list_rank.append(s[i:i+j+1])

list_rank.sort()
print(list_rank[K-1])

Submission status: Runtime Error

Solution code:
s = str(input())
K = int(input())
li = []
for i in range(1,K+1):
    for j in range(len(s)+1-K):
        li.append(s[j:j+i])
li = list(set(li))
li.sort()
print(li[K-1])

Submission status: Runtime Error

Solution code:
s = str(input())
K = int(input())
li = []
for i in range(1,K+1):
    for j in range(len(s)+1-K):
        li.append(s[j:j+i])
li = list(set(li))
li.sort()
print(li[K-1])

Submission status: Runtime Error

Solution code:
s = str(input())
K = int(input())
li = []
for i in range(0,len(s),1):
    for j in range(i+1,len(s)+1,1):
        li.append(s[i:j])
li = list(set(li))
li.sort()
print(li[K-1])

Submission status: Runtime Error

Solution code:
s = input()
k = int(input())
sub = set()
for i in range(len(s)):
  for j in range(1,k):
    sub.add(s[i:i+j])
print(sorted(list(sub))[k-1])

Submission status: Runtime Error

Solution code:
s = input()
k = int(input())
sub = set()
for i in range(n):
  for j in range(1,k):
    sub.add(s[i:i+j])
print(sorted(list(sub))[k-1])

Submission status: Runtime Error

Solution code:
from itertools import*
s=input()
k=int(input())
l=[]
for i in range(1,10):
    for t in range(len(s)+1-i):
        if len(set(s[t:t+i]))!=1:
            l.append(s[t:t+i])
for i in set(s):
    l.append(i)
print(sorted(set(l))[k-1])

Submission status: Runtime Error

Solution code:
from itertools import*
s=input()
k=int(input())
l=[]
for i in range(1,6):
    for t in range(len(s)+1-i):
        if len(set(s[t:t+i]))!=1:
            l.append(s[t:t+i])
for i in set(s):
    l.append(i)
print(sorted(set(l))[k-1])

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
typedef double dl;
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define MOD (ll)1000000007
#define lb lower_bound
#define ub upper_bound
#define dst distance
#define INF 1000000000

string S,a;
int K,n;
map<string,bool> M;

int RA[5010], tempRA[5010]; // rank array and temporary rank array
int SA[5010], tempSA[5010]; // suffix array and temporary suffix array
int c[5010]; // for counting/radix sort
void countingSort(int k) { // O(n)
	int i, sum, maxi = max(300, n); // up to 255 ASCII chars or length of n
	memset(c, 0, sizeof c); // clear frequency table
	for (i = 0; i < n; i++){
		c[i + k < n ? RA[i + k] : 0]++; // count the frequency of each integer rank
	}
	for (i = sum = 0; i < maxi; i++) {
		int t = c[i]; 
		c[i] = sum; 
		sum += t;
	}
	for (i = 0; i < n; i++) tempSA[c[SA[i]+k < n ? RA[SA[i]+k] : 0]++] = SA[i]; // shuffle the suffix array if necessary
	for (i = 0; i < n; i++) SA[i] = tempSA[i];// update the suffix array SA
}

void constructSA() {
	int i, k, r;
	for (i = 0; i < n; i++) RA[i] = S[i]; // initial rankings
	for (i = 0; i < n; i++) SA[i] = i; // initial SA: {0, 1, 2, ..., n-1}
	for (k = 1; k < n; k <<= 1) { // repeat sorting process log n times
		countingSort(k); // actually radix sort: sort based on the second item
		countingSort(0); // then (stable) sort based on the first item
		tempRA[SA[0]] = r = 0; // re-ranking; start from rank r = 0
		for (i = 1; i < n; i++) // compare adjacent suffixes
		tempRA[SA[i]] =  (RA[SA[i]] == RA[SA[i-1]] && RA[SA[i]+k] == RA[SA[i-1]+k]) ? r : ++r; // if same pair => same rank r; otherwise, increase r
		for (i = 0; i < n; i++) RA[i] = tempRA[i]; // update the rank array RA
		if (RA[SA[n-1]] == n-1) break;
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	//freopen("input.txt","r",stdin);
	cin >> S >> K;
	n = S.size();
	constructSA();
	for (int i = 0; i < n; ++i){
		a = "";
		for (int j = SA[i]; j < n; ++j){
			a += S[j];
			if(M[a])continue;
			--K;
			M[a] = 1;
			if (K == 0){cout << a; return 0;}
		}
	}
}

Submission status: Runtime Error

Solution code:

import sys
from collections import deque
import copy
import math

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [S] = [(input_raw[0])]
    input_raw = read_func().strip().split()
    [K] = [int(input_raw[0])]
##    if len(S) >= K:
##        min_s = "zzzzzzz"
##        for i in range(len(S) - K):
##            if S[i : i + K]< min_s:
##                min_s = S[i : i + K]
##        print min_s
##        return
##    else:
    sub_list = set([])
    for i in range(len(S)):
        for j in range(i + 1, len(S)):
            sub_list.add(S[i:j])

    sub_list = list(sub_list)
    sub_list.sort()
    print sub_list[K - 1]


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def f(r, a):
    if r[a] != a:
        r[a] = f(r, r[a])
    return r[a]


def union(r, x, y):
    a = f(r, x)
    b = f(r, y)
    if a != b:
        r[a] = b


n, m = list(map(int, input().split()))
p = list(map(int, input().split()))
r = [i for i in range(n)]

for i in range(m):
    x, y = list(map(int, input().split()))
    x = x - 1
    y = y - 1
    union(r, x, y)


c = 0
for i in range(n):
    if f(r, i) == f(r, p[i] - 1):
        c += 1

print(c)

Submission status: Runtime Error

Solution code:
n,k = [f(input())for f in [list,int]]

if len(n)<k:
    k -= len(n)
    b = []
    for i in n:
        if i != min(n):
            b.append(i)
    p = min(b)
else:
    p = min(n)

j = [[] for _ in range(n.count(p))]
l = 0
for i in range(len(n)):
    if p == n[i]:
        j[l] += n[i:i+k]
        l += 1

ans = min(j)
for i in range(k):
    print(ans[i], end='')

Submission status: Runtime Error

Solution code:
s = input()
K = int(input())
dict = []
n = len(s)
for i in range(n):
    if not s[i] in dict:
        dict.append(s[i])
dict = sorted(dict)
sub_dict=[]
result = []
# sub_dict.append([])
# for i in range(n-1):
#     if s[i] == dict[0]:
#         if not s[i+1] in sub_dict[0]:
#             sub_dict[0].append(s[i+1])
# sub_dict[0] = sorted(sub_dict[0])
# for i in range(n-1):
#     if s[i]==dict[0] and s[i+1]==sub_dict[0][0]:
#         for j in range(i+1,n):
#             if not s[i:j] in result:
#                 result.append(s[i:j])
# 
for d_i in range(len(dict)):
    if len(result) >=K:
        break
    sub_dict.append([])
    if n>1:
        for i in range(n-1):
            if s[i] == dict[d_i]:
                if not s[i+1] in sub_dict[d_i]:
                    sub_dict[d_i].append(s[i+1])
        sub_dict[d_i] = sorted(sub_dict[d_i])
        for i in range(n-1):
            if s[i]==dict[d_i] and s[i+1]==sub_dict[d_i][0]:
                for j in range(i+1,n+1):
                    if not s[i:j] in result:
                        result.append(s[i:j])
    else:
        result.append(s)
print(result[K-1])

Submission status: Runtime Error

Solution code:
from collections import Counter


def main():
    s = input()
    k = int(input())
    substr = []
    for l in range(len(s)):
        for r in range(l+1,len(s)+1):
            substr.append(s[l:r])
    c = Counter(substr)
    c = sorted(c.keys())
    print(c[k-1])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
s=input()
k=nu()
n=len(s)
z=set()
for i in range(n):
	pp=""
	for j in range(i,n):
		pp+=s[j]
		z.add(pp)
fin=list(z)
fin.sort()
print(fin[k-1])

Submission status: Runtime Error

Solution code:
s = str(input())
k = int(input())
sub = []
c = 5
if len(s)  < 5:
  c = len(s)
for i in range(c):
  for j in range(len(s)-i-1):
    sub.append(s[j:j+i+1])

sub = list(set(sub))
sub.sort()
print(sub[k-1])

Submission status: Runtime Error

Solution code:
def sub_k(string, I, K):
    temp = []
    for i in range(len(string)):
        if i-1+I == len(string):
            continue
        temp.append(string[i:i+I])
    return sorted(set(temp))[0:K]

def main(string, K):
    result = []
    for i in range(K):
        result += sub_k(string, i+1, K-i)
    print(sorted(set(result))[K-1])

string = input()
K = int(input())
main(string, K)

Submission status: Runtime Error

Solution code:
def sub_k(string, I, K):
    temp = []
    for i in range(len(string)):
        if i-1+I == len(string):
            continue
        temp.append(string[i:i+I])
    return sorted(set(temp))[0:K]

def main(string, K):
    for i in range(K):
        print(sub_k(string, i+1, K-i))

string = input()
K = input()
main(string, K)

Submission status: Runtime Error

Solution code:
class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		if self.table[x] < 0:
			return x
		else:
			self.table[x] = self.find(self.table[x]) #xをxの根に直接つなぐ
			return self.table[x]

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 == s2:
			return
		else:
			st1 = self.table[s1]
			st2 = self.table[s2]
			if st1 > st2:
				self.table[s2] = s1
			elif st1 < st2:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1


n, m = map(int, input().split())
p = list(map(int, input().split()))

uf = UnionFind(n)

for i in range(m):
	x, y = map(int, input().split())
	uf.union(x - 1, y - 1)

ans = 0
for i, pp in enumerate(p):
	if pp - 1 == i:
		ans += 1
	elif uf.find(pp - 1) == uf.find(i):
		ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		while self.table[x] >= 0:
			x = self.table[x]
		return x

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 == s2:
			return
		else:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
			elif self.table[s1] < self.table[s2]:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1


n, m = map(int, input().split())
p = list(map(int, input().split()))

uf = UnionFind(n)

for i in range(m):
	x, y = map(int, input().split())
	uf.union(x - 1, y - 1)

ans = 0
for i, pp in enumerate(p):
	if pp - 1 == i:
		ans += 1
	elif uf.find(pp - 1) == uf.find(i):
		ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
s = input().strip()
K = int(input())


def min_substring(s, l, num):
    substrings = list(set([s[i:i+l] for i in range(len(s)-l+1)]))
    substrings.sort()

    return substrings[num]




rank = 0
top = min_substring(s, 1, rank)
res = top
k = 1
l = 2

while k < K:
    substrings = list(set([s[i:i+l] for i in range(len(s)-l+1) if s[i:i+l-1] == res]))
    substrings.sort()

    if len(substrings) == 0:
        rank += 1
        top = min_substring(s, 1, rank)
        res = top
        k += 1
        continue
    else:
        for string in substrings:
            k += 1
            res = string
            break

        l += 1

print(res)

Submission status: Runtime Error

Solution code:
s = input().rstrip()
k = int(input())
result = []
for i in range(len(s)):
  for j in range(i+1,i+k):
    if i+k <= len(s):
      result.append(s[i:j])
result.sort()
print(result[k-1])

Submission status: Runtime Error

Solution code:
import sys
X = sys.stdin.readline() 
x = int(X)
n = 1
m = 1
ans = 1
for i in range(9):
    n=1
    b = i+2
    a = 1
    while n <= x:
        a+=1
        n = a**b
        if n<=x and n>=ans:
            ans = n
print(ans)

Submission status: Runtime Error

Solution code:
s = input()
print(sorted(list(set([s[i:j+1] for i in range(len(s)) for j in range(i,len(s))])))[int(input())-1])

Submission status: Runtime Error

Solution code:
s = input()
K = int(input())
print(sorted(list(set([s[i:j+1] for i in range(len(s)) for j in range(i,len(s))])))[K-1])

Submission status: Runtime Error

Solution code:
s = input()
print(sorted(set([s[i:j+1] for i in range(len(s)) for j in range(i,len(s))]))[int(input())-1])

Submission status: Runtime Error

Solution code:
s = input()
K = int(input())
ls = []
for i in range(1,len(s)+1):
    for j in range(i,len(s)+1):
        tmp = s[i:j]
        if tmp != "":
            ls.append(s[i:j])
print(sorted(list(set(ls)))[K-1])

Submission status: Runtime Error

Solution code:
S = str(input())
K = int(input())

sub = set()
for i in range(1,min(K, len(S))+1):
    for j in range(len(S)-K+1):
        sub.add(S[j:j+i])
m=list(sub)
m.sort()
print(m[K-1])

Submission status: Runtime Error

Solution code:
s = input()
K = int(input())
# substrings = {}
substrings = []
for i in range(1,6:
    for j in range(0,len(s)):
        if s[j:j+i] not in substrings:
            # substrings[s[j:j+1]] = True
            substrings.append(s[j:j+i])
print(sorted(substrings)[K-1])

Submission status: Runtime Error

Solution code:
import numpy as np
N, M = list(map(int, input().split()))
p = list(map(int, input().split()))
x = []
y = []
for _ in range(M):
    xi, yi = list(map(int, input().split()))
    x.append(xi - 1)
    y.append(yi - 1)

def count(l):
    out = 0
    for i, v in enumerate(l):
        if i + 1 == v:
            out += 1
    return out

def swap(l, a, b):
    va = l[a]
    vb = l[b]
    l1 = l.copy()
    l1[a] = vb
    l1[b] = va
    return l1

depth = 0
max_count = count(p)
max_d = M**5
children = [p]
next_children = []
while depth <= max_d:
    for child in children:
        for i in range(M):
            pi = swap(child, x[i], y[i])
            ci = count(pi)
            if ci > max_count:
                max_count = ci
	    if not pi in next_children:
                next_children.append(pi)
    depth += 1
    children = next_children
    next_chldren = []
    if max_count == len(p):
        break

print(max_count)

Submission status: Runtime Error

Solution code:
import numpy as np

s = input()
K = int(input())
L = len(s)

candidate = []

for l in range(1, K + 1):
    for j in range(0, L - l):
        candidate.append(s[j:j+l])

print(np.sort(candidate)[K-1])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Contents   : AtCoder Regular Contest C問題
Author     : KitauraHiromi
LastUpdate : 20180517
Since      : 20180517
"""
def head_char(substrs, k):
    dict = {}
    for i in range(len(substrs)):
        dict[substrs[i][0]] = 0
    for i in range(len(substrs)):
        dict[substrs[i][0]] += len(substrs[i])
    sum = 0
    pre_sum = 0
    pre_alph = ""
    for alph in sorted(dict.keys()):
        if sum > k:
            return (pre_alph, pre_sum)
        pre_sum = sum
        pre_alph = alph
        sum += dict[alph]
    return (pre_alph, pre_sum)

def find_substring(substrs, K, ret):
    # print("K", K, "ret", ret)
    if K <= 0:
        return ret
    head, k = head_char(substrs, K-1)
    # print("head:", head)
    idxes = [pos for pos, substr in enumerate(substrs) if substr[0] == head]
    new_substrs = [substrs[idx][1:] for idx in idxes]
    # print("new_substrs", new_substrs)
    # print(new_substrs, K-k)
    return find_substring(new_substrs, K-k-1, ret+head)

s = input()
K = int(input())
substrs = [s[i:] for i in range(len(s))]
print(find_substring(substrs, K, ""))

Submission status: Runtime Error

Solution code:
import numpy as np
import heapq


def ii():
    return int(input())


def lii():
    return list(map(int, input().split(' ')))


def lvi(N):
    l = []
    for _ in range(N):
        l.append(ii())
    return l


def lv(N):
    l = []
    for _ in range(N):
        l.append(input())
    return l


def main():
    s = input()
    K = ii()

    sub = []
    for i in range(len(s)):
        sub.append(s[i:])

    heapq.heapify(sub)
    minsub = heapq.heappop(sub)

    if len(minsub) >= K:
        print(minsub[:K])
        return

    cand = []
    for i in range(1, len(minsub)+1):
        cand.append(minsub[:i])
    K -= len(minsub)
    assert K > 0

    min2sub = heapq.heappop(sub)
    for i in range(1, len(min2sub)+1):
        if not min2sub[:i] in cand:
            cand.append(min2sub[:i])
            K -= 1
            if K == 0:
                print(min2sub[:i])
                return

    min3sub = heapq.heappop(sub)
    for i in range(1, len(min3sub)+1):
        if not min3sub[:i] in cand:
            cand.append(min3sub[:i])
            K -= 1
            if K == 0:
                print(min3sub[:i])
                return

    print(minsub, min2sub, min3sub)

    raise ValueError


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from itertools import accumulate

N = int(input())
balls = []

# 初期位置を覚えておく
placeB = [0] * N
placeW = [0] * N

# 入力処理 & 初期位置処理
for i in range(2*N):
    c, a = input().split()
    a = int(a)
    balls.append([c, a])
    if c == "B":
        placeB[a-1] = i
    else:
        placeW[a-1] = i


costB = [[0]*(2*N+1) for i in range(N+1)]  # i番目まででjより大きいB
costW = [[0]*(2*N+1) for i in range(N+1)]  # i番目まででjより大きいW

for i in range(N):
    for j in range(2*N):
        if balls[j][1] > i:
            if balls[j][0] == "B":
                costB[i][j+1] = 1
            else:
                costW[i][j+1] = 1

# 累積和
costB = [list(accumulate(cB)) for cB in costB]
costW = [list(accumulate(cW)) for cW in costW]

# dp
dp = [[float('inf')]*(N+1) for i in range(N+1)]
dp[0][0] = 0
for b in range(N+1):
    for w in range(N+1):
        if b > 0:
            dp[b][w] = min(dp[b][w], dp[b-1][w] + costB[b][placeB[b-1]] + costW[w][placeB[b-1]])
        if w > 0:
            dp[b][w] = min(dp[b][w], dp[b][w-1] + costW[w][placeW[w-1]] + costB[b][placeW[w-1]])

print(dp[N][N])

Submission status: Runtime Error

Solution code:
# ANSHUL GAUTAM
# IIIT-D
 
def get_all_substrings(input_string):
  length = len(input_string)
  return list([input_string[i:j+1] for i in range(length) for j in range(i,length)])


s = input()
K = int(input())  
l = get_all_substrings(s)
l = sorted(l)
L = []
for i in l:
	if(i not in L):
		L.append(i)
print(L[K-1])

Submission status: Runtime Error

Solution code:
import copy

n,m=map(int, input().split())
p=list(map(int, input().split()))
q=list()
for i in range(m):
    q.append(set(map(int, input().split())))
count=0
while count!=5000:
    a=q.pop()
    for j in q:
        if len(j&a) != 0:
            j |=a
            count=0
            break
    else:q=[a]+q
    if count>len(q): break
    count+=1

q2=copy.copy(set(p))
for i in q:
    q2 -= i
    
count2=len([i for i in q2 if i==p[i-1]])

for i in q:
    r=list()
    for j in list(i):
        r.append(p[j-1])
    #print(i,r)
    count2 += len(i&set(r))
print(count2)

Submission status: Runtime Error

Solution code:
def brute_force(s, K):
    substring_set = set()

    # brute-force
    for start in range(len(s)):
        # 5まででよかった...
        for length in range(1, 6):
            substring = s[start:start+length]
            substring_set.add(substring)

    substring_list = sorted(list(substring_set))
    print(substring_list)
    print(substring_list[K - 1])

brute_force(s, K)

Submission status: Runtime Error

Solution code:
s = input()
K = int(input())


def brute_force(s, K):
    substring_set = set()

    # brute-force
    for start in range(len(s)):
        # 5まででよかった...
        for length in range(len(s) - start + 1):
            if length == 0:
                substring = s[start]
            else:
                substring = s[start:start+length]
            substring_set.add(substring)
            if length == 4:
                break

    substring_list = sorted(list(substring_set))
    print(substring_list[K - 1])

brute_force(s, K)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

n, m = map(int, input().split())
p = [int(x) - 1 for x in input().split()]
g = [list() for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
v = [False] * n
s = set()
def dfs(i):
    if v[i]: return
    s.add(i)
    v[i] = True
    for k in g[i]: dfs(k)

c = 0
for i in range(n):
    if v[i]: continue
    s = set()
    dfs(i)
    t = {p[k] for k in s}
    c += len(s.intersection(t))
print(c)

Submission status: Runtime Error

Solution code:
s = list(input())
k = int(input())
sub = []
sub += s[:]
 
for j in range(2,K+1):
    charGram = [''.join(s[i:i+j]) for i in range(len(s)-1)]
    sub += charGram
sub = list(set(sub))
print(sorted(sub)[k-1])

Submission status: Runtime Error

Solution code:
s = input()
K = int(input())

def count(head):
    cnt = 0
    for i in range(len(s)):
        if i+len(head)-1<len(s) and s[i:i+len(head)]==head:
            cnt += len(s)-i
    return cnt

def solve50(head, K):
    #print('**', head, K)
    W = []
    for i in range(len(s)):
        if i+len(head)-1<len(s) and s[i:i+len(head)]==head:
            for j in range(i, len(s)):
                W.append(s[i:j+1])
                #print(' ', s[i:j+1])
    W = list(set(W))
    W.sort()
    #print(W)
    if len(W)>=K:
        return W[K-1], 0
    else:
        K -= len(W)
        return 0, K

def solve(head, K):
    #print('*', head, K)
    if count(head)<=50:
        return solve50(head, K)
    for a in alphabet:
        if head + a in s:
            #return solve(head + a, K)
            return head + a, -1


alphabet = 'abcdefghijklmnopqrstuvwxyz'

for a in alphabet:
    if not a in s:
        continue

    head = a
    while True:
        ans, K = solve(head, K)
        #print(ans, K)
        if K==0:
            print(ans)
            exit()
        elif K==-1:
            head = ans
        else:
            break

#print('*')