== include(page="template/taskheader" task_id="inter") ==

Fie $p$ o permutare a primelor $N$ numere naturale. Dacă se va aplica algoritmul Bubble Sort, se vor
interschimba elementele vecine ($p[i]$ şi $p[i+1]$, dacă $p[i] > p[i+1]$, pentru orice $i$, $1 ≤ i ≤ N$)

Fie $P$ o permutare a primelor $N$ numere naturale. Dacă se va aplica algoritmul Bubble Sort, se vor
interschimba elementele vecine ( $P[i]$ şi $P[i+1]$, dacă $P[i] > P[i+1]$, pentru orice $i$, $1 ≤ i ≤ N$)

până când $p$ devine permutarea identitate $(1, 2, 3, ... N)$. Pornind de permutarea identitate, date

fiind interschimbările făcute de algoritm, să se construiască permutarea originală $p$.

fiind interschimbările făcute de algoritm, să se construiască permutarea originală $P$.

h2. Date de intrare

Fişierul de intrare $inter.in$ ...

Fişierul de intrare $inter.in$ conţine două numere $n$ şi $m$ (numărul de elemente ale permutării,
respectiv numărul de interschimbări). Pe următoarele $m$ linii se află câte două numere $x$ şi $y$ cu
semnificaţia „$x$ se va interschimba cu $y$ atunci când vor fi vecini.”
 

h2. Date de ieşire

În fişierul de ieşire $inter.out$ ...

În fişierul de ieşire $inter.out$ se vor afla n numere separate prin spaţiu reprezentând permutarea originală.
 

h2. Restricţii

* $... ≤ ... ≤ ...$

* $3 ≤ n ≤ 1000$

h2. Exemplu
table(example). |_. inter.in |_. inter.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5 4
1 2
1 3
2 3
1 4
| 3 2 4 5 1

|
h3. Explicaţie