มีเกาะที่บีเวอร์อาศัยอยู่ $N$ เกาะ มีหมายเลขตั้งแต่ $0$ ถึง $N-1$ เกาะเหล่านี้เชื่อมกันด้วยสะพานสองทิศทาง $N-1$ แห่ง สามารถเดินทางระหว่างเกาะใด ๆ โดยใช้สะพานบางแห่งได้ แต่ละเกาะมีสะพานเชื่อมต่อโดยตรงไม่เกิน 18 แห่ง แต่ละเกาะมีบีเวอร์อาศัยอยู่หนึ่งตัว

บางครั้งบีเวอร์บางตัวจะมารวมกันบนเกาะแห่งหนึ่งเพื่อประชุม เมื่อบีเวอร์สามตัวพอดีมาประชุมกัน พวกมันจะไปรวมกันที่เกาะต่อไปนี้:

เกาะที่ทำให้จำนวนสะพานทั้งหมดที่บีเวอร์ทั้งสามต้องข้ามเพื่อมารวมกันมีค่าน้อยที่สุด (มีเกาะเช่นนี้เพียงแห่งเดียว)

สังเกตว่าเกาะนี้อาจเป็นเกาะที่บีเวอร์หนึ่งในสามตัวอาศัยอยู่ก็ได้

คุณสนใจว่าเกาะทั้ง $N$ เกาะเชื่อมกันด้วยสะพานอย่างไร คุณไม่สามารถไปตรวจสอบเกาะโดยตรงได้ จึงจะออกคำสั่งบางอย่างให้บีเวอร์ คำสั่งหนึ่งคำสั่งมีลักษณะดังนี้:

• คุณระบุเกาะสามแห่ง $u$, $v$ และ $w$ ($0\le u\le N-1$, $0\le v\le N-1$, $0\le w\le N-1$, $u\ne v$, $u\ne w$, $v\ne w$) แล้วให้บีเวอร์ที่อาศัยอยู่บนเกาะ $u$, $v$ และ $w$ มาประชุมกัน
• จากนั้นคุณจะเห็นเกาะที่บีเวอร์ทั้งสามมารวมกัน

คุณต้องการทราบว่าเกาะต่าง ๆ เชื่อมกันอย่างไร โดยใช้คำสั่งจำนวนน้อย

จงเขียนโปรแกรมที่รับจำนวนเกาะ สื่อสารกับบีเวอร์ และระบุว่าเกาะต่าง ๆ เชื่อมกันอย่างไร

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

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

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

void Solve(int N)

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

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

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

int Query(int u, int v, int w)

ฟังก์ชันนี้คืนหมายเลขเกาะที่บีเวอร์ซึ่งอาศัยอยู่บนเกาะทั้งสามที่คุณระบุไปรวมตัวกันเพื่อประชุม

• คุณระบุหมายเลข $u$, $v$ และ $w$ ของเกาะทั้งสามผ่านพารามิเตอร์ u, v และ w ตามลำดับ โดยต้องเป็นไปตาม $0\le u\le N-1$, $0\le v\le N-1$, $0\le w\le N-1$, $u\ne v$, $u\ne w$ และ $v\ne w$ มิฉะนั้นโปรแกรมของคุณจะถูกตัดสินว่าคำตอบผิด [1]
• ต้องเรียกฟังก์ชัน Query ไม่เกิน $100\,000$ ครั้ง มิฉะนั้นโปรแกรมของคุณจะถูกตัดสินว่าคำตอบผิด [2]

void Bridge(int u, int v)

คุณใช้ฟังก์ชันนี้เพื่อตอบว่าเกาะต่าง ๆ เชื่อมกันด้วยสะพานอย่างไร

• พารามิเตอร์ u และ v หมายความว่าเกาะ $u$ และ $v$ เชื่อมกันโดยตรงด้วยสะพาน
• หากไม่เป็นไปตาม $0\le u<v\le N-1$ โปรแกรมของคุณจะถูกตัดสินว่าคำตอบผิด [3]
• หากเกาะ $u$ และ $v$ ไม่ได้เชื่อมกันโดยตรงด้วยสะพาน โปรแกรมของคุณจะถูกตัดสินว่าคำตอบผิด [4]
• หากเรียกฟังก์ชัน Bridge ด้วยพารามิเตอร์ $u$ และ $v$ คู่เดิมหลายครั้ง โปรแกรมของคุณจะถูกตัดสินว่าคำตอบผิด [5]
• เนื่องจากมีสะพาน $N-1$ แห่ง จึงต้องเรียกฟังก์ชัน Bridge จำนวน $N-1$ ครั้งพอดี หากเมื่อฟังก์ชัน Solve สิ้นสุดการทำงาน จำนวนครั้งที่เรียกฟังก์ชัน Bridge ไม่เท่ากับ $N-1$ โปรแกรมของคุณจะถูกตัดสินว่าคำตอบผิด [6]

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

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

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

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

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

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

เมื่อคอมไพล์สำเร็จ จะได้ไฟล์ปฏิบัติการ grader

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

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

ตัวตรวจตัวอย่างอ่านข้อมูลต่อไปนี้จากอินพุตมาตรฐาน

$$ \begin{array}{ll} N & \\ A_0 & B_0 \\ \vdots & \\ A_{N-2} & B_{N-2} \end{array} $$

$A_i$ และ $B_i$ ($0\le i\le N-2$) หมายความว่าเกาะ $A_i$ และ $B_i$ เชื่อมกันโดยตรงด้วยสะพาน

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

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

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

หากโปรแกรมของคุณถูกตัดสินว่าคำตอบผิดหลายประเภท ตัวตรวจตัวอย่างจะรายงานเพียงประเภทเดียว

ข้อจำกัด

ดูนิยามของ $A_i$ และ $B_i$ ในหัวข้อ “ข้อมูลนำเข้าสำหรับตัวตรวจตัวอย่าง”

• $3\le N\le 2\,000$
• $0\le A_i<B_i\le N-1$ ($0\le i\le N-2$)
• สามารถเดินทางระหว่างเกาะใด ๆ โดยใช้สะพานบางแห่งได้
• แต่ละเกาะมีสะพานเชื่อมต่อโดยตรงไม่เกิน 18 แห่ง

งานย่อย

1. (7 คะแนน) $N\le 7$
2. (10 คะแนน) $N\le 50$
3. (12 คะแนน) $N\le 300$

4. (71 คะแนน) ไม่มีข้อจำกัดเพิ่มเติม

5. สำหรับงานย่อยที่ 1, 2 และ 3 หากโปรแกรมของคุณถูกต้องสำหรับทุกกรณีทดสอบในงานย่อยนั้น คุณจะได้คะแนนเต็ม

6. สำหรับงานย่อยที่ 4 หากโปรแกรมของคุณถูกต้องสำหรับทุกกรณีทดสอบ คะแนนของคุณจะเป็นดังต่อไปนี้ โดยให้ $X$ เป็นจำนวนครั้งสูงสุดที่เรียกฟังก์ชัน Query ในกรณีทดสอบหนึ่งกรณี

   • 49 คะแนน หาก $40\,000<X\le100\,000$ และ
   • 71 คะแนน หาก $X\le40\,000$

ตัวอย่าง

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

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

5
0 1
0 2
1 3
1 4

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