คำอธิบายโจทย์
จงสร้างตัวต้านทานที่มีค่าความต้านทาน $\sqrt{D}\,[\Omega]$ โดยใช้เฉพาะตัวต้านทานที่มีค่าความต้านทาน $1\,[\Omega]$ เท่านั้น
กำหนดจำนวนเต็มบวก $D$ จงสร้างกราฟไม่ระบุทิศทางที่เชื่อมโยงกันหนึ่งกราฟซึ่งสอดคล้องกับเงื่อนไขทั้งหมดต่อไปนี้ ภายใต้ข้อจำกัดของโจทย์ข้อนี้ สามารถพิสูจน์ได้ว่ามีกราฟดังกล่าวอยู่เสมอ
- จำนวนจุดยอด $N$ อยู่ระหว่าง $2$ ถึง $300$ (รวม $2$ และ $300$ ด้วย) และแต่ละจุดยอดมีหมายเลขที่แตกต่างกันตั้งแต่ $1$ ถึง $N$
- จำนวนเส้นเชื่อม $M$ มีค่าไม่เกิน $300$ โดยอนุญาตให้มีเส้นเชื่อมวนกลับหาตัวเอง (self-loops) และเส้นเชื่อมซ้ำ (multiple edges) ได้
- "ความต้านทานสมมูลจากจุดยอด $1$ ไปยังจุดยอด $N$" ซึ่งนิยามไว้ด้านล่าง มีค่าคลาดเคลื่อนสัมบูรณ์ไม่เกิน $\pm 10^{-6}$ จาก $\sqrt{D}$
ให้ $G$ เป็นกราฟไม่ระบุทิศทางที่เชื่อมโยงกันซึ่งมี $n$ จุดยอด และ $m$ เส้นเชื่อม ($n \ge 2$) และสมมติว่าเส้นเชื่อมที่ $j$ เชื่อมระหว่างจุดยอด $a_j, b_j$ พิจารณาการกำหนดจำนวนจริง $V_i$ ($i = 1, 2, \dots, n$) ให้กับแต่ละจุดยอดของกราฟ $G$ และจำนวนจริง $I_j$ ($j = 1, 2, \dots, m$) ให้กับแต่ละเส้นเชื่อม เพื่อทำให้สมการทั้งหมดต่อไปนี้เป็นจริง:
- $I_j = V_{a_j} - V_{b_j} \quad (j = 1, 2, \dots, m)$
- $\sum_{b_j=i} I_j - \sum_{a_j=i} I_j = 0 \quad (i = 2, 3, \dots, n - 1)$
- $\sum_{b_j=n} I_j - \sum_{a_j=n} I_j = 1$
สามารถพิสูจน์ได้ว่ามีการกำหนดค่าดังกล่าวอยู่เสมอ และค่าของ $V_1 - V_n$ จะถูกกำหนดได้อย่างเดียวเท่านั้น เรานิยามค่านี้ว่า "ความต้านทานสมมูลจากจุดยอด $1$ ไปยังจุดยอด $n$"
ข้อมูลนำเข้า
ข้อมูลนำเข้าประกอบด้วยจำนวนเต็มบวก $D$ เพียงตัวเดียว ($1 \le D \le 5000$)
ข้อมูลส่งออก
ในบรรทัดแรก ให้พิมพ์จำนวนจุดยอด $N$ และจำนวนเส้นเชื่อม $M$ ของกราฟที่สร้างขึ้น ตามลำดับนี้ โดยคั่นด้วยช่องว่าง
ในแต่ละบรรทัดของ $M$ บรรทัดถัดไป บรรทัดที่ $i$ ($i = 1, 2, \dots, M$) จะต้องระบุจุดปลายทั้งสองของเส้นเชื่อมที่ $i$ โดยคั่นด้วยช่องว่าง
หากมีกราฟที่สอดคล้องกับเงื่อนไขหลายกราฟ สามารถพิมพ์กราฟใดก็ได้
ตัวอย่าง
ข้อมูลนำเข้า 1
1
ข้อมูลส่งออก 1
4 5 1 2 1 3 2 3 2 4 3 4
หมายเหตุ
ต่อไปนี้คือแผนภาพแสดงข้อมูลส่งออกของตัวอย่างที่ 1
การที่ความต้านทานสมมูลจากจุดยอด $1$ ไปยังจุดยอด $n$ มีค่าเท่ากับ $1\,[\Omega]$ สามารถอธิบายได้ดังนี้:
- เนื่องจากตัวต้านทานทุกตัวมีความต้านทาน $1\,[\Omega]$ และจากความสมมาตร ศักย์ไฟฟ้าที่จุดยอด $2$ และ $3$ จึงเท่ากัน ดังนั้นตัวต้านทานที่อยู่ระหว่างจุดยอดทั้งสองจึงสามารถถือเสมือนว่าไม่มีอยู่ได้
- ส่งผลให้วงจรลดรูปเหลือสองกิ่งที่ต่อขนานกัน โดยแต่ละกิ่งประกอบด้วยตัวต้านทาน $1\,[\Omega]$ สองตัวต่ออนุกรมกัน
- ความต้านทานสมมูลของตัวต้านทาน $1\,[\Omega]$ สองตัวที่ต่ออนุกรมกันคือ $2\,[\Omega]$ และความต้านทานสมมูลของตัวต้านทาน $2\,[\Omega]$ สองตัวที่ต่อขนานกันคือ $1\,[\Omega]$
ข้อมูลส่งออกต่อไปนี้ก็ถือว่าถูกต้องเช่นกัน:
2 1 1 2