A serious incident happened at Taro's house, which loves steamed buns. One of the three steamed buns offered at the Buddhist altar in the Japanese-style room was gone. When Taro, who was aiming for a snack someday, started an investigation to find the criminal, it turned out that there were many people who entered the Japanese-style room that day. So I decided to ask everyone to give the following form of testimony to find out the order in which these suspects entered the room.

Suspect A's testimony "I entered the room before Suspect B."

One of the suspects (?) Is a calico cat, so I can't testify, but fortunately Taro saw the last time he entered the room.

From these testimonies, Taro decided to guess the order in which he entered the room and use it for the investigation.

For example, if there are 6 suspects and Tama is suspect 2, the following testimony is obtained.

Testimony of Suspect 5 "I entered the room before 2."
Suspect 1's testimony "I entered the room before 4."
Testimony of Suspect 3 "I entered the room before 5."
Suspect 4's testimony "I entered the room before 2."
Suspect 1's testimony "I entered the room before 6."
Suspect 6's testimony "I entered the room before 4."
Testimony of Suspect 3 "I entered the room before 4."


Putting this testimony together, the order in which they entered the room

* 3 → 5 → 1 → 6 → 4 → 2
* 1 → 6 → 3 → 4 → 5 → 2
* 3 → 1 → 6 → 5 → 4 → 2



You can narrow down to several possibilities.

From the testimony of all suspects except Tama (Suspect 2), estimate the order in which they entered the room and write a program that outputs one of the possible orders. However, although some suspects may give multiple testimonies, all testimonies shall be true and consistent.



Input

The input is given in the following format:


m
n
x1 y1
x2 y2
::
xn yn


The first line gives the number of suspects m (m ≤ 20), and the second line gives the number of testimonies n (n ≤ 100). The following n lines are given the contents of the i-th testimony, xi and yi, respectively, on the first line. xi yi represents the testimony that "suspect xi (I) entered before suspect yi".

Output

Print the number of the suspect who entered the room first, the number of the suspect who entered the room second, ..., and the number of the suspect who entered the room second, in order on one line.

Example

Input

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


Output

3
5
1
6
4
2

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import sys, math, os
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):
		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
		if predecessor[target] == -1:
			return []
		path = [target]
		while path[0] != source:
			path = [predecessor[path[0]]] + path[:]
		return path

	def TopologicalSort(self):
		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)


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
			if in_degree[e] == 0 and processed[e] == False:
				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:
			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)))
main(sys.argv[1:])


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)


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)


import sys
import os
import math
m = int(input())
n = int(input())
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:
	for (i, node) in enumerate(G):
		if not printed[i] and len(node) == 0:
			print(i + 1)
			printed[i] = True
			for node in G:
				if i in node:
					node.remove(i)
if False in printed:
	i = printed.index(False)
	print(i + 1)


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)


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()


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])


visited = []

def dfs(v):
	for i in edges[v]:
		if i not in visited:
			dfs(i)
	visited.append(v)
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)))


visited = []

def dfs(v):
	for i in edges[v]:
		if i not in visited:
			dfs(i)
	visited.append(v)
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)))