Problem:


太郎君の執念

 まんじゅう好きの太郎くんの家でたいへんな事件がおきました。和室の仏壇に供えてあった3つのまんじゅうのうち1つが無くなっていたのです。いつかはおやつにいただこうと狙っていた太郎くんが犯人を見つけるため捜査を始めると、その日、和室に入った人が何人もいることが分かりました。そこで、これらの容疑者が部屋に入った順序を調べるため、全員に次のような形式の証言をしてもらうことにました。

 容疑者 A の証言 「私は容疑者 B より先に部屋に入った。」

 容疑者の一人(?)は三毛猫のタマなので証言はできませんが、幸運にも最後に部屋に入ったところを太郎くんは見ていました。

 太郎くんはこれらの証言から、部屋に入った順番を推測して捜査に役立てることにしました。

 例えば、6 人の容疑者がいてタマを容疑者 2 とした場合、以下のような証言が得られたとします。

 容疑者 5 の証言 「私は 2 より先に部屋に入った。」

 容疑者 1 の証言 「私は 4 より先に部屋に入った。」

 容疑者 3 の証言 「私は 5 より先に部屋に入った。」

 容疑者 4 の証言 「私は 2 より先に部屋に入った。」

 容疑者 1 の証言 「私は 6 より先に部屋に入った。」

 容疑者 6 の証言 「私は 4 より先に部屋に入った。」

 容疑者 3 の証言 「私は 4 より先に部屋に入った。」

 この証言をつなぎ合わせると、部屋に入った順序は

 
3→5→1→6→4→2

 
1→6→3→4→5→2

 
3→1→6→5→4→2

   など、何通りかの可能性に絞り込むことができます。

タマ (容疑者 2) 以外の容疑者全員の証言から、部屋に入った順番を推測し、可能性のある順番の 1 つを出力するプログラムを作成してください。ただし、複数の証言をする容疑者がいるかもしれませんが、どの証言も真実であり矛盾していないものとします。

Input

入力は以下の形式で与えられます。

m
n
x1 y1
x2 y2
:
xn yn

1 行目に容疑者の人数 m (m ≤ 20)、2 行目に証言の数 n (n ≤ 100) が与えられます。
続く n 行に i 個目の証言の内容 xi,  yi がそれぞれ１行に与えられます。xi yi は「容疑者 xi(私)は容疑者 yi より先に入った」という証言を表します。

Output

最初に部屋に入った容疑者の番号、2 番目に部屋に入った容疑者の番号、...、m 番目に部屋に入った容疑者の番号をそれぞれ１行に順番に出力してください。

Sample Input

6
7
5 2
1 4
3 5
4 2
1 6
6 4
3 4

Output for the Sample Input

3
5
1
6
4
2



Sample input:
6
7
5 2
1 4
3 5
4 2
1 6
6 4
3 4


Sample output:
3
5
1
6
4
2

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

def satisfy_conditions(ans, part_evidences):
    for i in range(len(part_evidences)):
        x, y = part_evidences[i]
        xi, yi = ans.index(x), ans.index(y)
        if xi > yi:
            return False
    return True


if __name__ == '__main__':
    m = int(input())
    n = int(input())
    evidences = []
    ans = list(range(1, m + 1))
    ans.remove(2)
    ans.append(2)
    for i in range(n):
        x, y = map(int, input().split())
        evidences.append((x, y))

    for i in range(n): # i???????????\????????????????????°??????
        x, y = evidences[i]
        xi, yi = ans.index(x), ans.index(y)
        if xi < yi:
            continue
        # xi???yi????????????????????£???????????????yi???xi?????????????????£?????????
        # ????????????????????????(x)??????????????????????????????(y)?????????????????????
        # y...x??¨????????¶???
        # ???????????????xi???????????????y?????\??????
        for j in range(xi + 1, n - 1):  # j?????\????????´??????????£?
            # ??????????????????
            ans_copy = ans[:]
            ans_copy.insert(j, y)
            ans_copy.remove(y)
            #print(ans_copy)
            # ????????\???????????¶????????????????????????
            if satisfy_conditions(ans_copy, evidences[:i]):
                print('\n'.join(map(str, ans_copy)))

Submission status: Wrong Answer

Solution code:
def f(a, b):
    s = ''.join(ans)
    if not (s.find(a) < s.find(b)):
        ans.remove(a)
        ans.insert(s.find(b), a)

ans = [str(i+1) for i in range(input())]
for i in range(input()):
    f(*(raw_input().split()))
else:
    for v in ans:
        print v

Submission status: Wrong Answer

Solution code:
def f(a, b):
    s = ''.join(ans)
    if not (s.find(a) < s.find(b)):
        ans.remove(a)
        ans.insert(s.find(b), a)

ans = [str(i+1) for i in range(input())]
ans.remove('2')
ans.append('2')
for i in range(input()):
    f(*(raw_input().split()))
else:
    for v in ans:
        print v

Submission status: Wrong Answer

Solution code:
def f(a, b):
    s = ''.join(ans)
    if not (s.find(a) < s.find(b)):
        ans.remove(a)
        ans.insert(s.find(b), a)

ans = [str(i+1) for i in range(input())]
for i in range(input()):
    f(*(raw_input().split()))
for v in ans:
    print v

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import math

m = int(input())
n = int(input())

# Manage people who entered earlier than me in a list
G = [[] for i in range(m)]

for i in range(n):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    G[y].append(x)

printed = [False] * m

while printed.count(False) > 1:
    # Delete node with degree 0
    for i, node in enumerate(G):
        if not printed[i] and len(node) == 0:
            print(i+1)
            printed[i] = True

            # Erase his existence
            for node in G:
                if i in node:
                    node.remove(i)
# cat
print(2)

Submission status: Wrong Answer

Solution code:
count = int(input())
comment_count = int(input())

input_data = [input().split(" ") for _ in range(comment_count)]
input_data = [(int(item1), int(item2)) for item1, item2 in input_data]

people_list = [2]

search_list = [False] * (count + 1)
search_list[2] = True

index_set = {0: 2}

while 0 < comment_count:
    data_list = [item for item in input_data if search_list[item[1]]]

    search_list = [False] * (count + 1)
    comment_count -= len(data_list)

    for i, you in data_list:

        if i not in index_set:
            people_list.append(i)
            index_set[i] = len(people_list) - 1
        else:
            index1 = index_set[i]
            index2 = index_set[you]

            if index1 < index2:
                people_list.insert(index2 + 1, i)
                people_list.pop(index1)

                index_set[i] = index2 + 1

        search_list[i] = True

people_list = [str(item) for item in people_list]
print("\n".join(people_list))

Submission status: Wrong Answer

Solution code:
m = [i+1 for i in range(int(raw_input()))]
n = int(raw_input())
for i in range(n):
	x,y = map(int, raw_input().split())
	if m.index(x) > m.index(y):
		r = m.pop(m.index(x))
		m.insert(m.index(y),r)
for i in m: print m

Submission status: Wrong Answer

Solution code:
m = [i+1 for i in range(int(raw_input()))]
n = int(raw_input())
for i in range(n):
	x,y = map(int, raw_input().split())
	if m.index(x) > m.index(y):
		r = m.pop(m.index(x))
		m.insert(m.index(y),r)
for i in m: print i

Submission status: Wrong Answer

Solution code:
m = [i+1 for i in range(int(raw_input()))]
m[0],m[1] = m[1],m[0]
n = int(raw_input())
for i in range(n):
	x,y = map(int, raw_input().split())
	if m.index(x) > m.index(y):
		r = m.pop(m.index(x))
		m.insert(m.index(y),r)
for i in m: print i

Submission status: Wrong Answer

Solution code:
m = [i+1 for i in range(int(raw_input()))]
m[0],m[1] = m[1],m[0]
xy = [map(int, raw_input().split()) for i in range(int(raw_input()))]
xy = sorted(xy,key = lambda x:x[1])
for x,y in xy:
	if m.index(x) > m.index(y):
		m.insert(m.index(y),m.pop(m.index(x)))
for i in m: print i

Submission status: Wrong Answer

Solution code:
m = [i+1 for i in range(int(raw_input()))]
xy = [map(int, raw_input().split()) for i in range(int(raw_input()))]
xy = sorted(xy,key = lambda x:x[1])
for x,y in xy:
	if m.index(x) > m.index(y):
		m.insert(m.index(y),m.pop(m.index(x)))
for i in m: print i

Submission status: Wrong Answer

Solution code:
import itertools
m = input()
exp = "True"
for i in range(input()):
	x,y = map(int,raw_input().split())
	exp += " and N[" + str(x-1) + "] > N[" + str(y-1) + "]"
for N in itertools.permutations(range(m),m):
	if eval(exp):
		for i in N:
			print i
		break

Submission status: Wrong Answer

Solution code:
import itertools
m = input()
exp = "True"
for i in range(input()):
	x,y = map(int,raw_input().split())
	exp += " and N[" + str(x-1) + "] < N[" + str(y-1) + "]"
for N in itertools.permutations(range(m),m):
	if eval(exp):
		for i in N:
			print i
		break

Submission status: Wrong Answer

Solution code:
import itertools
m = input()
exp = "True"
for i in range(input()):
	x,y = map(int,raw_input().split())
	exp += " and N[" + str(x-1) + "] < N[" + str(y-1) + "]"
for N in itertools.permutations(range(m),m):
	if eval(exp):
		for i in N:
			print i + 1
		break

Submission status: Wrong Answer

Solution code:
import itertools
m = input()
exp = "True"
for i in range(input()):
	x,y = map(int,raw_input().split())
	exp += " and N[" + str(x-1) + "] > N[" + str(y-1) + "]"
for N in itertools.permutations(range(m),m):
	if eval(exp):
		for i in N:
			print i + 1
		break

Submission status: Wrong Answer

Solution code:
import itertools
m = input()
exp = "True"
for i in range(input()):
	x,y = map(int,raw_input().split())
	exp += " and N[" + str(x-1) + "] < N[" + str(y-1) + "]"
for N in itertools.permutations(range(m),m):
	if eval(exp):
		for i in N[::-1]:
			print i + 1
		break

Submission status: Wrong Answer

Solution code:
import itertools
m = input()
exp = "True"
for i in range(input()):
	x,y = map(int,raw_input().split())
	exp += " and N[" + str(x-1) + "] > N[" + str(y-1) + "]"
for N in itertools.permutations(range(m),m):
	if eval(exp):
		for i in N[::-1]:
			print i + 1
		break

Submission status: Wrong Answer

Solution code:
m = input()
S = [[1]*m for i in range(m)]
for i in range(input()):
	x,y = map(int,raw_input().split())
	S[y-1][x-1] = 0
	for j in range(m):
		if S[x-1][j] == 0: S[y-1][j] = 0
		if S[j][y-1] == 0: S[j][x-1] = 0
A = [sum([S[h][i] for h in range(m)]) for i in range(m)]
rank = m
ans = [0]*m
M = range(m)
while M:
	for i in M:
		if A[i] >= rank:
			rank -= 1
			ans[rank] = i+1
			del M[M.index(i)]
			break
for i in range(m): print ans[i]

Submission status: Wrong Answer

Solution code:
m = input()
S = [[1]*m for i in range(m)]
for i in range(input()):
	x,y = map(int,raw_input().split())
	S[y-1][x-1] = 0
	for j in range(m):
		if S[x-1][j] == 0: S[y-1][j] = 0
		if S[j][y-1] == 0: S[j][x-1] = 0
A = [sum(S[i]) for i in range(m)]
rank = 1
M = range(m)
while M:
	for i in M:
		if m - A[i] + 1 <= rank:
			print i + 1
			rank += 1
			del M[M.index(i)]
			break

Submission status: Wrong Answer

Solution code:
m = input()
S = [[1]*m for i in range(m)]
for i in range(input()):
	x,y = map(int,raw_input().split())
	S[y-1][x-1] = 0
	for j in range(m):
		if S[x-1][j] == 0: S[y-1][j] = 0
		if S[j][y-1] == 0: S[j][x-1] = 0
R = [sum(S[i]) for i in range(m)]
C = [sum([S[j][i] for j in range(m)]) for i in range(m)]
for r in range(m):
	for c in range(m):
		if S[r][c] == 0: continue
		if (r == c and R[r] + C[r] > m+2) or (r != c and  R[r] + C[r] > m+1 and R[c] + C[c] > m+1):
			S[r][c] = 0
			R[r] -= 1
			C[c] -= 1
rank = sorted([[C[i],i+1] for i in range(m)])
for r,i in rank: print i

Submission status: Wrong Answer

Solution code:
m = input()
S = [[1]*m for i in range(m)]
for i in range(input()):
	x,y = map(int,raw_input().split())
	S[y-1][x-1] = 0
	for j in range(m):
		if S[x-1][j] == 0: S[y-1][j] = 0
		if S[j][y-1] == 0: S[j][x-1] = 0
R = [sum(S[i]) for i in range(m)]
C = [sum([S[j][i] for j in range(m)]) for i in range(m)]
while sum(R) + sum(C) > m*(m+1):
	flag = 0
	for r in range(m):
		if R.count(R[r]) == 1: continue
		for c in range(m):
			if S[r][c] == 0 and C.count(C[c]) == 1: continue
			if r != c and  R[r] + C[r] > m+1 and R[c] + C[c] > m+1:
				S[r][c] = 0
				R[r] -= 1
				C[c] -= 1
				flag = 1
				break
	if flag == 0: break
rank = sorted([[C[i],i+1] for i in range(m)])
for r,i in rank: print i

Submission status: Wrong Answer

Solution code:
def solve(a):
	if len(a) == m: return a
	for x,y in xy:
		if y in a and x not in a:
			r = solve(a + [x])
			if r:
				return r

m = input()
xy = [map(int,raw_input().split()) for i in range(input())]
ans = solve([2])[::-1]
for i in ans: print i

Submission status: Wrong Answer

Solution code:
def solve(a):
	if len(a) == m: return a
	for x,y in xy:
		if y in a and x not in a:
			r = solve([x] + a)
			if r:
				return r

m = input()
xy = [map(int,raw_input().split()) for i in range(input())]
for i in range(m):
	ans = solve([i])
	if ans:
		break
for i in ans: print i

Submission status: Wrong Answer

Solution code:
def solve(a,M):
	if len(a) == m: return a
	for x,y in xy:
		if x in a and y in a and a.index(x) > a.index(y):
			break
	else:
		return max([solve([M[i]] + a,M[:i]+M[i+1:]) for i in range(len(M))])

m = input()
xy = [map(int,raw_input().split()) for i in range(input())]
ans = solve([],range(1,m+1))
for i in ans: print i

Submission status: Time Limit Exceeded

Solution code:
import itertools
m = input()
exp = "True"
for i in range(input()):
	x,y = map(int,raw_input().split())
	exp += " and N[" + str(x-1) + "] < N[" + str(y-1) + "]"
for N in itertools.permutations(range(m),m):
	if eval(exp):
		ans = sorted([[N[i],i+1] for i in range(m)])
		for n,i in ans:
			print i
		break

Submission status: Time Limit Exceeded

Solution code:
m = input()
S = [[1]*m for i in range(m)]
for i in range(input()):
	x,y = map(int,raw_input().split())
	S[y-1][x-1] = 0
	for j in range(m):
		if S[x-1][j] == 0: S[y-1][j] = 0
		if S[j][y-1] == 0: S[j][x-1] = 0
R = [sum(S[i]) for i in range(m)]
C = [sum([S[j][i] for j in range(m)]) for i in range(m)]
while sum(R) + sum(C) > m*(m+1):
	for r in range(m):
		if R.count(R[r]) == 1: continue
		for c in range(m):
			if S[r][c] == 0 and C.count(C[c]) == 1: continue
			if r != c and  R[r] + C[r] > m+1 and R[c] + C[c] > m+1:
				S[r][c] = 0
				R[r] -= 1
				C[c] -= 1
				break
rank = sorted([[C[i],i+1] for i in range(m)])
for r,i in rank: print i

Submission status: Time Limit Exceeded

Solution code:
m = input()
S = [[1]*m for i in range(m)]
for i in range(input()):
	x,y = map(int,raw_input().split())
	S[y-1][x-1] = 0
	for j in range(m):
		if S[x-1][j] == 0: S[y-1][j] = 0
		if S[j][y-1] == 0: S[j][x-1] = 0
R = [sum(S[i]) for i in range(m)]
C = [sum([S[j][i] for j in range(m)]) for i in range(m)]
while sum(R) + sum(C) > m*(m+1):
	for r in range(m):
		if R.count(R[r]) == 1: continue
		for c in range(m):
			if S[r][c] == 0: continue
			if r != c and  R[r] + C[r] > m+1 and R[c] + C[c] > m+1:
				S[r][c] = 0
				R[r] -= 1
				C[c] -= 1
				break
rank = sorted([[C[i],i+1] for i in range(m)])
for r,i in rank: print i

Submission status: Time Limit Exceeded

Solution code:
m = input()
S = [[1]*m for i in range(m)]
for i in range(input()):
	x,y = map(int,raw_input().split())
	S[y-1][x-1] = 0
	for j in range(m):
		if S[x-1][j] == 0: S[y-1][j] = 0
		if S[j][y-1] == 0: S[j][x-1] = 0
R = [sum(S[i]) for i in range(m)]
C = [sum([S[j][i] for j in range(m)]) for i in range(m)]
while sum(R) + sum(C) > m*(m+1):
	for r in range(m):
		for c in range(m):
			if S[r][c] == 0: continue
			if r != c and  R[r] + C[r] > m+1 and R[c] + C[c] > m+1:
				S[r][c] = 0
				R[r] -= 1
				C[c] -= 1
rank = sorted([[C[i],i+1] for i in range(m)])
for r,i in rank: print i

Submission status: Time Limit Exceeded

Solution code:
m = input()
S = [[1]*m for i in range(m)]
for i in range(input()):
	x,y = map(int,raw_input().split())
	S[y-1][x-1] = 0
	for j in range(m):
		if S[x-1][j] == 0: S[y-1][j] = 0
		if S[j][y-1] == 0: S[j][x-1] = 0
R = [sum(S[i]) for i in range(m)]
C = [sum([S[j][i] for j in range(m)]) for i in range(m)]
while sum(R) + sum(C) > m*(m+1):
	for r in range(m):
		for c in range(m):
			if r != c and S[r][c] == 1 and  R[r] + C[r] > m+1 and R[c] + C[c] > m+1:
				S[r][c] = 0
				R[r] -= 1
				C[c] -= 1
rank = sorted([[C[i],i+1] for i in range(m)])
for r,i in rank: print i

Submission status: Time Limit Exceeded

Solution code:
def solve(a,M):
	for x,y in xy:
		if x in a and y in a and a.index(x) > a.index(y):
			break
	else:
		if len(a) == m: return a
		return max([solve([M[i]] + a,M[:i]+M[i+1:]) for i in range(len(M))])

m = input()
xy = [map(int,raw_input().split()) for i in range(input())]
ans = solve([],range(1,m+1))
for i in ans: print i

Submission status: Time Limit Exceeded

Solution code:
def solve(a,M):
	for x,y in xy:
		if x in a and (y not in a or a.index(x) > a.index(y)):
			break
	else:
		if len(a) == m: return a
		return max([solve([M[i]] + a,M[:i]+M[i+1:]) for i in range(len(M))])

m = input()
xy = [map(int,raw_input().split()) for i in range(input())]
M = range(m)
ans = solve([],range(1,m+1))
for i in ans: print i

Submission status: Accepted

Solution code:
m=int(raw_input())
n=int(raw_input())
A=sorted([map(int,raw_input().split()) for _ in range(n)])
X=[]
while A:
  a1,a2=map(set,zip(*A))
  B=a2-a1
  na=len(A)
  for i in range(na)[::-1]:
    e0,e1=A[i]
    if e1 in B:
      if e1 not in X: X.append(e1)
      del A[i]
X=list(set(range(1,m+1))-set(X))+X[::-1]
for e in X: print e

Submission status: Accepted

Solution code:
m=input()
A=[map(int,raw_input().split()) for _ in range(input())]
X=[]
while A:
  a1,a2=map(set,zip(*A))
  for e in A:
    if e[1] in a2-a1:
      if e[1] not in X: X.append(e[1])
      A.remove(e)
X=list(set(range(1,m+1))-set(X))+X[::-1]

for e in X: print e

Submission status: Accepted

Solution code:
m=input()
A=[map(int,raw_input().split()) for _ in [0]*input()]
X=[]
while A:
  a1,a2=map(set,zip(*A))
  for e in A:
    if e[1] in a2-a1:
      if e[1] not in X: X.append(e[1])
      A.remove(e)

for e in list(set(range(1,m+1))-set(X))+X[::-1]: print e

Submission status: Accepted

Solution code:
visited = []

def dfs(v):
    for i in edges[v]:
        if i not in visited:
            dfs(i)
    visited.append(v)

if __name__ == '__main__':
    m = int(input())
    n = int(input())
    evidences = []
    edges = [[] for i in range(m)]
    for i in range(n):
        x, y = map(int, input().split())
        evidences.append((x, y))
        edges[x - 1].append(y - 1)
    for i in range(m):
        if i not in visited:
            dfs(i)
    ans = reversed([i + 1 for i in visited])
    print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
visited = []

def dfs(v):
    for i in edges[v]:
        if i not in visited:
            dfs(i)
    visited.append(v)

if __name__ == '__main__':
    m = int(input())
    n = int(input())
    edges = [[] for i in range(m)]
    for i in range(n):
        x, y = map(int, input().split())
        edges[x - 1].append(y - 1)
    for i in range(m):
        if i not in visited:
            dfs(i)
    ans = reversed([i + 1 for i in visited])
    print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
dic = {}
for i in range(input()):
    dic[i+1] = []
for i in range(input()):
    x, y = map(int, raw_input().split())
    dic[y].append(x)

del dic[2]
ans  = []
while True:
    lis = sorted(dic.items(), key=lambda x: len(x[1]))
    k = lis[0][0]
    del dic[k]
    ans.append(k)
    if not dic: break
    for v in dic.values():
        if k in v:
            v.remove(k)

for v in ans:
    print v
else:
    print 2

Submission status: Accepted

Solution code:
dic = {}
for i in range(input()):
    dic[i+1] = []
for i in range(input()):
    x, y = map(int, raw_input().split())
    dic[y].append(x)
else:
    del dic[2]

ans  = []
while True:
    lis = sorted(dic.items(), key=lambda x: len(x[1]))
    k = lis[0][0]
    del dic[k]
    ans.append(k)
    if not dic: break
    for v in dic.values():
        if k in v:
            v.remove(k)

for v in ans:
    print v
else:
    print 2

Submission status: Accepted

Solution code:
m=int(raw_input())
n=int(raw_input())
A=[[] for i in range(m+1)]
B=[1]+range(3,m+1)
ans=[2]
for i in range(n):
    a,b=map(int,raw_input().split())
    if b!=2:
        A[a].append(b)
while(len(B)!=0):
    kb=[]
    for b in B:
        if A[b]==[]:
            ans.append(b)
            kb.append(b)
            for a in A:
                if b in a:
                    a.remove(b)
    for k in kb:
        B.remove(k)
ans.reverse()
for a in ans:
    print a

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import math

m = int(input())
n = int(input())

# Manage people who entered earlier than me in a list
G = [[] for i in range(m)]

for i in range(n):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    G[y].append(x)

printed = [False] * m

while printed.count(False) > 1:

    # Delete node with degree 0
    for i, node in enumerate(G):
        if not printed[i] and len(node) == 0:
            print(i+1)
            printed[i] = True

            # Erase his existence
            for node in G:
                if i in node:
                    node.remove(i)

# cat
if False in printed:
    i = printed.index(False)
    print(i+1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0119
"""
import sys
from collections import deque


def bfs(u, result, out_edge, in_degree, processed):
    q = deque()
    q.append(u)
    processed[u] = True
    while q:
        u = q.popleft()
        result.append(u)
        for e in out_edge[u]:
            in_degree[e] -= 1   #  ?????¨?????????????????????(u)?????????????????¨???u?????\?¶????(e)????????\????¬???°???1???????????¨?????????
            if in_degree[e] == 0 and processed[e] == False: #  ??\????¬???°???1??????????????????0???????????°??????????????????????¬??????????????£??????????
                processed[e] = True
                q.append(e)


def solve(m, in_degree, out_edge):
    result = []
    processed = [False for _ in range(m+1)] #  ???????????????????????????????????????????????°

    for i, u in enumerate(in_degree[1:], start=1):
        if u == 0 and processed[i] == False: #  ??\????¬???°???0???????????????
            bfs(i, result, out_edge, in_degree, processed)
    return result


def main(args):
    m = int(input())
    n = int(input())
    in_degree = [0 for _ in range(m+1)] #  ????????????????????\????¬???°
    out_edge = [[] for _ in range(m+1)] #  ???????????????????????????(??\?¶?)?????????????????????
    for _ in range(n):
        s, t = [int(x) for x in input().split(' ')]
        out_edge[s].append(t)
        in_degree[t] += 1

    result = solve(m, in_degree, out_edge)
    print('\n'.join(map(str, result)))

if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# Aizu Problem 00119: Taro's Obsession
#
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")

class DirectedGraph():
    def __init__(self):
        self.edges = {}

    def AddNode(self, node):
        if node not in self.edges:
            self.edges[node] = []

    def GetNodes(self):
        return list(self.edges.keys())

    def GetEdges(self):
        return self.edges

    def AddEdge(self, node1, node2):
        if node1 not in self.GetNodes():
            self.AddNode(node1)
        if node2 not in self.edges[node1]:
            self.edges[node1].append(node2)

    def RemoveEdge(self, node1, node2):
        if node1 not in self.edges or node2 not in self.edges[node1]:
            print("ERROR: can't remove edge", node1, "->", node2)
            print(self.edges)
            return
        self.edges[node1].remove(node2)

    def OutDegree(self, node):
        return len(self.edges[node])

    def InDegree(self, node):
        deg = 0
        for node2 in self.GetNodes():
            if node in self.GetNeighbors(node2):
                deg += 1
        return deg

    def GetNeighbors(self, node):
        return self.edges.get(node, [])
            
    def GetPath(self, source, target):
        # find path by BFS:
        predecessor = {node: -1 for node in self.GetNodes()}
        predecessor[source] = 0
        visited = {node: False for node in self.GetNodes()}
        queue = [source]
        while len(queue) > 0:
            current = queue.pop(0)
            visited[current] = True
            for neighbor in self.GetNeighbors(current):
                if not visited[neighbor] and neighbor not in queue:
                    queue.append(neighbor)
                    predecessor[neighbor] = current
                if neighbor == target:
                    queue = []
                    break
        # build path from predecessor info:
        if predecessor[target] == -1:
            return []
        path = [target]
        while path[0] != source:
            path = [predecessor[path[0]]] + path[:]
        return path

    def TopologicalSort(self):
        # determine topological sorting of graph by Kahn's algorithm;
        # edges are removed by this algorithm
        L = []
        S = [node for node in self.GetNodes() if self.InDegree(node) == 0]
        while len(S) > 0:
            n = S.pop(0)
            L.append(n)
            for m in self.GetNeighbors(n)[:]:
                self.RemoveEdge(n, m)
                if self.InDegree(m) == 0:
                    S.append(m)
        for node in self.GetNodes():
            if self.edges[node] != []:
                print("ERROR: graph has cycle!", self.edges)
                return
        return L


m = int(input())
n = int(input())
G = DirectedGraph()
for __ in range(n):
    a, b = [int(_) for _ in input().split()]
    G.AddEdge(a, b)
tsort = G.TopologicalSort()
for k in tsort:
    print(k)

Submission status: Accepted

Solution code:
m = int(input())
n = int(input())

X = [0 for i in range(n)]
Y = [0 for i in range(n)]

for l in range(n):
    X[l],Y[l] = [int(i) for i in input().split()]

ans = []
while True:
    flag = True
    for i in range(1, m+1):
        if not (i in Y) and not (i in ans):
            ans.append(i)

            for j in range(len(X))[::-1]:
                if X[j] == i:
                    X.pop(j)
                    Y.pop(j)
            flag = False
            break
    if flag:
        break

for i in range(len(ans)):
    print(ans[i])

Submission status: Accepted

Solution code:
#トポロジカルソート

m = int(input())
n = int(input())

edges = [[] for _ in range(m)]
for _ in range(n):
  x, y = map(int, input().split())
  edges[x - 1].append(y - 1)

visited = [False for _ in range(m)]
sorted_lst = []

def visit(i):
  if not visited[i]:
    visited[i] = True
    for to in edges[i]:
      visit(to)
    sorted_lst.append(i)

for i in range(m):
  visit(i)

sorted_lst.reverse()

for i in sorted_lst:
  print(i + 1)

Submission status: Accepted

Solution code:
# AOJ 0119: Taro's Obsession
# Python3 2018.6.20 bal4u

def topological_sort(V, to):
	cnt = [0]*V
	for i in range(V):
		for j in to[i]:	cnt[j] += 1
	Q = []
	for i in range(V):
		if cnt[i] == 0:
			Q.append(i)
	while len(Q) > 0:
		i = Q[0]
		del Q[0]
		print(i+1)
		for k in to[i]:
			cnt[k] -= 1
			if cnt[k] == 0:	Q.append(k)

m = int(input())
to = [[] for i in range(m)]
n = int(input())
for i in range(n):
	x, y = list(map(int, input().split()))
	to[x-1].append(y-1)
topological_sort(m, to)

Submission status: Accepted

Solution code:
m = input()
n = input()
in_edges = [[] for _ in xrange(m+1)]
in_edges[2] = [i for i in xrange(1,m+1) if not i == 2]
for _ in xrange(n):
    x,y = map(int,raw_input().split())
    if not x in in_edges[y]:
        in_edges[y].append(x) 
row = []
while not len(row) == m:
    for i in xrange(1,m+1):
        if in_edges[i] == [] and not i in row:
            row.append(i)
            for ii in xrange(1,m+1):
                if i in in_edges[ii]:
                    in_edges[ii].remove(i)
print "\n".join(map(str,row))

Submission status: Accepted

Solution code:
m = int(raw_input())
n = int(raw_input())
a = [[False] * (m + 1) for _ in range(m + 1)]
b = [0] * (m + 1)
for _ in range(n):
    x, y = map(int, raw_input().split())
    a[y][x] = True
    b[y] += 1
for i in range(m):
    for j in range(m):
        if b[j + 1] == 0:
            print j + 1
            b[j + 1] = -1
            for k in range(m):
                if a[k + 1][j + 1]:
                    b[k + 1] -= 1

Submission status: Accepted

Solution code:
def solve(a,M):
	for x,y in xy:
		if x in a and (y not in a or a.index(x) > a.index(y)):
			break
	else:
		if len(a) == m: return a
		for i in range(len(M)):
			r =  solve([M[i]] + a,M[:i]+M[i+1:])
			if r:
				return r

m = input()
xy = [map(int,raw_input().split()) for i in range(input())]
M = range(m)
ans = solve([],range(1,m+1))
for i in ans: print i

Submission status: Accepted

Solution code:
def solve(a,M):
	for x,y in xy:
		if x in a and (y not in a or a.index(x) > a.index(y)): break
	else:
		if len(a) == m: return a
		for i in range(len(M)):
			r =  solve([M[i]] + a,M[:i]+M[i+1:])
			if r: return r
m = input()
xy = [map(int,raw_input().split()) for i in range(input())]
for i in solve([],range(1,m+1)): print i

Submission status: Accepted

Solution code:
def solve(a):
	if len(a) == m: return a
	for i in M-set(a):
		for x,y in xy:
			if x == i and y not in a: break
		else:
			r = solve([i]+a)
			if r: return r
m = input()
M = set(range(1,m+1))
xy = [map(int,raw_input().split()) for i in range(input())]
for i in solve([]): print i

Submission status: Accepted

Solution code:
def solve(a):
	for i in M-set(a):
		for x,y in xy:
			if x == i and y not in a: break
		else:
			r = solve([i]+a)
			if r: return r
	return a
m = input()
M = set(range(1,m+1))
xy = [map(int,raw_input().split()) for i in range(input())]
for i in solve([]): print i

Submission status: Accepted

Solution code:
def solve(a):
	for i in M-set(a):
		if any(x == i and y not in a for x,y in xy): continue
		r = solve([i]+a)
		if r: return r
	return a
m = input()
M = set(range(1,m+1))
xy = [map(int,raw_input().split()) for i in range(input())]
for i in solve([]): print i

Submission status: Accepted

Solution code:
from collections import deque
def solve():
    M = int(input())
    G = [[] for i in range(M)]
    deg = [0]*M
    N = int(input())
    for i in range(N):
        x, y = map(int, input().split())
        G[x-1].append(y-1)
        deg[y-1] += 1
    que = deque()
    ans = []
    for i in range(M):
        if deg[i] == 0:
            que.append(i)
    while que:
        v = que.popleft()
        ans.append(v+1)
        for w in G[v]:
            deg[w] -= 1
            if deg[w] == 0:
                que.append(w)
    print(*ans, sep='\n')
solve()

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy
from test.support import _MemoryWatchdog

BIG_NUM = 2000000000
HUGE_NUM = 99999999999999999
MOD = 1000000007
EPS = 0.000000001
sys.setrecursionlimit(100000)


class Edge:
    def __init__(self,arg_to):
        self.to = arg_to

M = int(input())
N = int(input())

in_num = [0]*(M+1)
G = [[] for _ in range(M+1)] #隣接グラフ

for _ in range(N):
    x,y = map(int,input().split())
    in_num[y] += 1
    G[x].append(Edge(y))

Q = deque()
for i in range(1,M+1):
    if in_num[i] == 0:
        Q.append(i)

while len(Q) > 0:
    node_id = Q.popleft()
    print("%d"%(node_id))
    for edge in G[node_id]:
        in_num[edge.to] -= 1
        if in_num[edge.to] == 0:
            Q.append(edge.to)

Submission status: Accepted

Solution code:
m = int(input())
n = int(input())
edges = [[] for _ in range(m)]
for _ in range(n):
    x,y = map(int,input().split())
    edges[x-1].append(y-1)
L = []
visited = [False]*m
def visit(node):
    if not visited[node]:
        visited[node] = True
        for nn in edges[node]:
            visit(nn)
        L.append(node)
for node in range(m):
    visit(node)
for e in L[::-1]:
    print(e+1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import math

m = int(input())
n = int(input())

# Manage people who entered earlier than me in a list
G = [[] for i in range(m)]

for i in range(n):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    G[y].append(x)

printed = [False] * m

while printed.count(False) > 1:
    # Delete node with degree 0
    for i, node in enumerate(G):
        if not printed[i] and len(node) == 0:
            print(i+1)
            printed[i] = True

            # Erase his existence
            for node in G:
                if i in node:
                    node.remove(i)

# cat
i = printed.index(False)
print(i+1)

Submission status: Runtime Error

Solution code:
m = [i+1 for i in range(int(raw_input()))]
n = int(raw_input())
for i in range(n):
	x,y = map(int, raw_input().split())
	if m.index(x) > m.index(y):
		r = m.pop(m.index(x))
		m.insert(m.index(y),r)
for i in range(n):
	print m[i]