ห้องปฏิบัติการของ Professor JOI กำลังศึกษาแร่ $N$ ชนิด โดยมีแร่แต่ละชนิดอยู่ 2 แผ่น รวมทั้งหมด $2N$ แผ่น ซึ่งมีหมายเลขตั้งแต่ $1$ ถึง $2N$

วันหนึ่ง ผู้ช่วย Bitaro ทำกล่องที่บรรจุแร่ทั้ง $2N$ แผ่นตก จึงไม่ทราบว่าแผ่นใดเป็นแร่ชนิดเดียวกับแผ่นใด

ห้องปฏิบัติการมีอุปกรณ์ที่สามารถนับจำนวนชนิดของแร่เมื่อใส่แร่บางแผ่นลงไปได้ โดยวัดความยาวคลื่นที่แร่แต่ละชนิดดูดกลืน Bitaro ต้องการหาคู่แร่ชนิดเดียวกันทั้ง $N$ คู่จากแร่ $2N$ แผ่น ในตอนเริ่มต้นไม่มีแร่แผ่นใดอยู่ในอุปกรณ์ Bitaro สามารถดำเนินการต่อไปนี้ได้:

• ใส่แร่หนึ่งแผ่นลงในอุปกรณ์ แล้วทราบว่ามีแร่อยู่ในอุปกรณ์กี่ชนิด
• นำแร่หนึ่งแผ่นออกจากอุปกรณ์ แล้วทราบว่ามีแร่อยู่ในอุปกรณ์กี่ชนิด

เพื่อไม่ให้ Professor JOI พบว่า Bitaro ก่อเรื่องยุ่งยาก Bitaro จึงสามารถดำเนินการเหล่านี้ได้รวมกันไม่เกิน $1\,000\,000$ ครั้ง

จงเขียนโปรแกรมที่รับจำนวนชนิดของแร่ แล้วใช้อุปกรณ์เพื่อหาคู่แร่ชนิดเดียวกันทั้งหมด

รายละเอียดการเขียนโปรแกรม

คุณต้องส่งไฟล์หนึ่งไฟล์

ไฟล์ต้องมีชื่อว่า minerals.cpp และต้องเขียนฟังก์ชันต่อไปนี้ โปรแกรมต้อง include ไฟล์ minerals.h

• void Solve(int N)

  ฟังก์ชันนี้จะถูกเรียกหนึ่งครั้งพอดีสำหรับแต่ละกรณีทดสอบ

  • พารามิเตอร์ N แทน $N$ ซึ่งเป็นจำนวนชนิดของแร่

โปรแกรมของคุณสามารถเรียกใช้ฟังก์ชันต่อไปนี้ได้

• int Query(int x)

  สำหรับหมายเลขแผ่นแร่ที่คุณระบุ หากแผ่นแร่นั้นอยู่ในอุปกรณ์แล้ว ฟังก์ชันนี้จะนำแผ่นนั้นออก มิฉะนั้นจะใส่แผ่นนั้นลงในอุปกรณ์ จากนั้นจะคืนค่าจำนวนชนิดของแร่ที่อยู่ในอุปกรณ์

  • คุณระบุหมายเลข $x$ ของแผ่นแร่ผ่านพารามิเตอร์ x โดยต้องเป็นไปตาม $1 \le x \le 2N$ มิฉะนั้นโปรแกรมจะได้รับผลตัดสิน Wrong Answer [1]
  • ห้ามเรียกฟังก์ชัน Query เกิน $1\,000\,000$ ครั้ง มิฉะนั้นโปรแกรมจะได้รับผลตัดสิน Wrong Answer [2]

• void Answer(int a, int b)

  ใช้ฟังก์ชันนี้เพื่อตอบคู่แร่ชนิดเดียวกัน

  • พารามิเตอร์ a และ b ระบุว่าแผ่นแร่ที่ $a$ และแผ่นแร่ที่ $b$ เป็นแร่ชนิดเดียวกัน โดยต้องเป็นไปตาม $1 \le a \le 2N$ และ $1 \le b \le 2N$ มิฉะนั้นโปรแกรมจะได้รับผลตัดสิน Wrong Answer [3] หากมีค่าใดปรากฏมากกว่าหนึ่งครั้งเมื่อนับรวมทั้ง a และ b โปรแกรมจะได้รับผลตัดสิน Wrong Answer [4] หากระบุแผ่นแร่ที่เป็นคนละชนิดกัน โปรแกรมจะได้รับผลตัดสิน Wrong Answer [5]

ต้องเรียกฟังก์ชัน Answer จำนวน $N$ ครั้งพอดี หากเมื่อฟังก์ชัน Solve ทำงานจบแล้ว จำนวนครั้งที่เรียกฟังก์ชัน Answer ไม่เท่ากับ $N$ โปรแกรมจะได้รับผลตัดสิน Wrong Answer [6]

ข้อควรทราบที่สำคัญ

• โปรแกรมสามารถเขียนฟังก์ชันอื่นเพื่อใช้ภายใน หรือใช้ตัวแปรส่วนกลางได้
• โปรแกรมห้ามใช้ข้อมูลนำเข้ามาตรฐานและข้อมูลส่งออกมาตรฐาน และห้ามสื่อสารกับไฟล์อื่นด้วยวิธีใดก็ตาม อย่างไรก็ตาม โปรแกรมสามารถส่งข้อมูลสำหรับดีบักไปยังช่องข้อผิดพลาดมาตรฐานได้

การคอมไพล์และการทดลองรัน

คุณสามารถดาวน์โหลดไฟล์เก็บถาวรจากเว็บไซต์การแข่งขัน ซึ่งมีโปรแกรมตรวจตัวอย่างสำหรับทดสอบโปรแกรมของคุณ ไฟล์เก็บถาวรนี้ยังมีไฟล์ซอร์สโค้ดตัวอย่างของโปรแกรมของคุณด้วย

โปรแกรมตรวจตัวอย่างคือไฟล์ grader.cpp เพื่อทดสอบโปรแกรมของคุณ ให้วาง grader.cpp, minerals.cpp และ minerals.h ไว้ในไดเรกทอรีเดียวกัน แล้วใช้คำสั่งต่อไปนี้เพื่อคอมไพล์โปรแกรม

g++ -std=gnu++14 -O2 -o grader grader.cpp minerals.cpp

เมื่อคอมไพล์สำเร็จ จะได้ไฟล์โปรแกรมที่เรียกทำงานได้ชื่อ grader

โปรดทราบว่าโปรแกรมตรวจจริงแตกต่างจากโปรแกรมตรวจตัวอย่าง โปรแกรมตรวจตัวอย่างจะทำงานเป็นโพรเซสเดียว โดยอ่านข้อมูลจากข้อมูลนำเข้ามาตรฐานและเขียนผลลัพธ์ไปยังข้อมูลส่งออกมาตรฐาน

ข้อมูลนำเข้าสำหรับโปรแกรมตรวจตัวอย่าง

โปรแกรมตรวจตัวอย่างอ่านข้อมูลต่อไปนี้จากข้อมูลนำเข้ามาตรฐาน

$$ \begin{array}{ll} N &\\ X_1 & Y_1\\ \vdots &\\ X_N & Y_N \end{array} $$

$X_i$ และ $Y_i$ ($1 \le i \le N$) ระบุว่าแผ่นแร่ที่ $X_i$ และแผ่นแร่ที่ $Y_i$ เป็นแร่ชนิดเดียวกัน

ข้อมูลส่งออกของโปรแกรมตรวจตัวอย่าง

เมื่อโปรแกรมจบการทำงานสำเร็จ โปรแกรมตรวจตัวอย่างจะเขียนข้อมูลต่อไปนี้ไปยังข้อมูลส่งออกมาตรฐาน (ใส่เครื่องหมายอัญประกาศเพื่อความชัดเจน)

• หากโปรแกรมของคุณถูกตัดสินว่าถูกต้อง จะเขียนจำนวนครั้งที่เรียกฟังก์ชัน Query ในรูปแบบ “Accepted: 100”
• หากโปรแกรมของคุณได้รับผลตัดสิน Wrong Answer จะเขียนชนิดของข้อผิดพลาดในรูปแบบ “Wrong Answer [1]”

หากโปรแกรมของคุณได้รับผลตัดสิน Wrong Answer หลายชนิด โปรแกรมตรวจตัวอย่างจะรายงานเพียงชนิดเดียว

ข้อจำกัด

ดูคำนิยามของ $X_i$ และ $Y_i$ ได้ในหัวข้อ “ข้อมูลนำเข้าสำหรับโปรแกรมตรวจตัวอย่าง”

• $1 \le N \le 43\,000$
• $1 \le X_i \le 2N$ ($1 \le i \le N$)
• $1 \le Y_i \le 2N$ ($1 \le i \le N$)
• $X_i \ne X_j$ ($1 \le i<j \le N$)
• $Y_i \ne Y_j$ ($1 \le i<j \le N$)
• $X_i \ne Y_j$ ($1 \le i \le N$, $1 \le j \le N$)

งานย่อย

1. (6 คะแนน) $N \le 100$
2. (25 คะแนน) $N \le 15\,000$, $1 \le X_i \le N$, $N+1 \le Y_i \le 2N$ ($1 \le i \le N$)
3. (9 คะแนน) $N \le 15\,000$
4. (30 คะแนน) $N \le 38\,000$
5. (5 คะแนน) $N \le 39\,000$
6. (5 คะแนน) $N \le 40\,000$
7. (5 คะแนน) $N \le 41\,000$
8. (5 คะแนน) $N \le 42\,000$
9. (10 คะแนน) ไม่มีข้อจำกัดเพิ่มเติม

ตัวอย่างการสื่อสาร

ต่อไปนี้คือข้อมูลนำเข้าตัวอย่างสำหรับโปรแกรมตรวจตัวอย่าง และการเรียกฟังก์ชันที่สอดคล้องกัน

ข้อมูลนำเข้า 1

4
1 5
2 6
3 4
7 8

ตัวอย่างการเรียกฟังก์ชัน