Есептің шарты

$1$-ден $N$-ге дейін нөмірленген $N$ доп бар. Сондай-ақ ішіне қанша доп салса да сыятын $N$ жәшік бар, жәшіктер де $1$-ден $N$-ге дейін нөмірленген.

Бастапқыда $i$-ші жәшікте ($1 \le i \le N$) $i$-ші доп жатқан.

JOI жоғары мектебінің оқушысы Аой осы күйден бастап жәшіктер мен доптарға $M$ рет амал қолданды. $j$-ші амал ($1 \le j \le M$) келесідей орындалды:

• Ішінде $X_j$ добы бар жәшікті тауып, сол жәшіктен $X_j$ добын алып шығады. Содан кейін $X_j$ добын $Y_j$ жәшігіне салады.

Аой барлық $M$ амалды орындап болғаннан кейін, $N$ доптың әрқайсысы қай жәшікте жатқанын табыңыз.

Шектеулер

• $1 \le N \le 2000$.
• $1 \le M \le 2000$.
• $1 \le X_j \le N$ ($1 \le j \le M$).
• $1 \le Y_j \le N$ ($1 \le j \le M$).
• Енгізілетін мәндердің барлығы бүтін сандар.

Кіріс деректер

Кіріс деректер стандартты кірістен келесі форматта беріледі:

N M
X_1 Y_1
X_2 Y_2
:
X_M Y_M

Шығыс деректер

$N$ жол шығарыңыз. $i$-ші жолда ($1 \le i \le N$) Аой барлық $M$ амалды аяқтағаннан кейін $i$-ші доп жатқан жәшіктің нөмірін шығарыңыз.

Мысалдар

Кіріс мысалы 1

3 4
1 2
3 2
2 1
1 3

Шығыс мысалы 1

3
1
2

Бастапқыда $1$-ші жәшікте $1$-ші доп, $2$-ші жәшікте $2$-ші доп, ал $3$-ші жәшікте $3$-ші доп болған.

Аой төмендегідей $4$ амал орындады:

• $1$-ші амалда $1$-ші допты $1$-ші жәшіктен алып, $2$-ші жәшікке салды.
• $2$-ші амалда $3$-ші допты $3$-ші жәшіктен алып, $2$-ші жәшікке салды.
• $3$-ші амалда $2$-ші допты $2$-ші жәшіктен алып, $1$-ші жәшікке салды.
• $4$-ші амалда $1$-ші допты $2$-ші жәшіктен алып, $3$-ші жәшікке салды.

Барлық амалдар аяқталған соң, $1$-ші доп $3$-ші жәшікте, $2$-ші доп $1$-ші жәшікте, ал $3$-ші доп $2$-ші жәшікте жатыр. Сондықтан жаңа жол арқылы осы ретпен $3, 1, 2$ шығарылады.

Кіріс мысалы 2

3 3
1 1
2 2
3 3

Шығыс мысалы 2

1
2
3

Барлық амалдар аяқталған соң, $1$-ші доп $1$-ші жәшікте, $2$-ші доп $2$-ші жәшікте, ал $3$-ші доп $3$-ші жәшікте жатыр. Сондықтан жаңа жол арқылы осы ретпен $1, 2, 3$ шығарылады.

Кіріс мысалы 3

4 2
1 3
2 4

Шығыс мысалы 3

3
4
3
4

Кіріс мысалы 4

4 8
1 3
3 2
2 4
2 3
4 1
2 1
1 4
3 3

Шығыс мысалы 4

4
1
3
1