== 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$)
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$.

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$.

h2. Date de intrare

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.”

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 ca $x$ se va interschimba cu $y$ atunci când vor fi vecini.

h2. Date de ieşire

h2. Restricţii

* $3 ≤ n ≤ 1000$

* $3 ≤ N ≤ 1000$
* $M ≤ N^2^$

h2. Exemplu

1 3
2 3
1 4

| 3 2 4 5 1

| 3 2 4 1 5

|

h3. Explicaţie

h3. Algoritmul BubbleSort

...

==code(c)|bool sortat = 0;
while(!sortat) {
    sortat = 1;
    for(int i = 1; i <= n - 1; ++i)
        if(v[i] > v[i + 1]) {
           swap(v[i], v[i + 1]);
           sortat = 0;
        }
     }
==

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

9276