รายละเอียดปัญหา

มีลูกบอล $N$ ลูก ซึ่งมีหมายเลขกำกับตั้งแต่ $1$ ถึง $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$) ให้แสดงหมายเลขของกล่องที่มีลูกบอลหมายเลข $i$ อยู่หลังจากที่อาโออิทำการดำเนินการครบทั้ง $M$ ครั้งแล้ว

ตัวอย่างข้อมูลนำเข้าและข้อมูลส่งออก

ตัวอย่างข้อมูลนำเข้า 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