증거 기반 순위

코치는 스포츠 순위에 진절머리가 났다. 이런 근거 없는 순위를 만드는 사람들은 그냥 제정신이 아니라고 생각한다. 코치의 의견으로는 순위 변동은 오직 증거에 근거해야 한다. 예를 들어 $4$위 팀이 $1$위 팀과 경기해서 졌다고 하자. 왜 순위가 바뀌어야 하는가? "더 나쁜" 팀이 "더 좋은" 팀에게 졌으니 순위에 아무런 변화가 없어야 한다. 달리 말하면 순서가 바뀌어야 한다는 증거가 없는데 왜 바꾸겠는가? 뭔가를 바꾸는 경우는, 가령 $4$위 팀이 $1$위 팀을 이겼을 때뿐이다. 이제 순위가 바뀌어야 한다는 증거가 생겼다! 구체적으로 $1$위 팀은 $4$위 팀 바로 아래로 가야 하고(이를 뒷받침하는 증거가 생겼다), $2$위부터 $4$위까지의 팀은 각각 한 칸씩 올라간다. 그 결과 원래 $1$위 팀은 이제 $4$위, 자신을 이긴 팀보다 한 칸 아래가 되고, 원래 $4$위 팀은 이제 $3$위가 된다. 현재 $1$위부터 $3$위까지의 팀들의 상대적 위치는 변하지 않는다. 바뀌어야 한다는 증거가 없기 때문이다.

이 과정을 일반화하면, $n$위 팀이 $m$위 팀을 이겼다고 하자. $n < m$이면 순위에 변화가 없어야 하고, $n > m$이면 $m+1, m+2, \ldots, n$위의 모든 팀이 한 칸씩 올라가고 원래 $m$위 팀이 $n$위로 이동한다.

예를 들어 $5$개 팀이 처음에 T$1$(최고), T$2$, T$3$, T$4$, T$5$(최하) 순으로 순위가 매겨져 있다고 하자. T$4$가 T$1$을 이겼다면 위에서 설명한 대로 새로운 순위는 T$2$, T$3$, T$4$, T$1$, T$5$가 된다. 이제 다음 경기에서 T$3$이 T$1$을 이겼다고 하자. 이 후 순위는 변하지 않아야 한다. 순위가 더 높은 팀이 순위가 더 낮은 팀을 이겼기 때문이다. 그 다음 경기에서 T$5$가 T$3$을 이기면 새로운 순위는 T$2$, T$4$, T$1$, T$5$, T$3$이 되고, 이런 식으로 계속된다.

코치는 이 방식을 구현하는 프로그램을 작성할 준비가 다 되어 있었지만, 그때 잉글랜드 프리미어 리그의 무승부에 대한 소식을 들었다. 그를 마지막으로 본 모습은 창밖을 바라보며 움직이지 않고 서 있는 것이었다. 프로그램은 여러분이 작성해야 할 것 같다.

입력의 첫 줄에는 두 양의 정수 $n$ $m$ ($n, m \leq 100$)이 주어지며, 이는 팀의 수와 진행된 경기의 수를 나타낸다. 팀 이름은 $\mbox{T}1, \mbox{T}2, \ldots, \mbox{T}n$이고, 처음에 각 팀 $\mbox{T}i$는 순위에서 $i$번째 위치에 있다(즉, 팀 $\mbox{T}1$이 $1$위이고 팀 $\mbox{T}n$이 최하위이다). 첫 줄 다음에는 시간 순서대로 진행된 경기 $m$개를 나타내는 $m$개의 줄이 주어진다. 각 줄은 $\mbox{T}i$ $\mbox{T}j$ ($1 \leq i,j \leq n, i \neq j$) 형태이며, 팀 $\mbox{T}i$가 팀 $\mbox{T}j$를 이겼음을 나타낸다.

팀들의 최종 순위를 한 줄에 출력한다. 팀 이름은 공백 하나로 구분한다.