อย่างที่ทราบกันดีว่า ปัญหา APSP (วิถีสั้นที่สุดระหว่างทุกคู่จุดยอด) มีความเชื่อมโยงอย่างลึกซึ้งกับการคูณเมทริกซ์แบบ min+ วันนี้เราต้องการให้คุณแก้ปัญหาต่อไปนี้:
กำหนด $x$ จงสร้างกราฟเชื่อมต่อแบบไม่มีทิศทางและไม่มีน้ำหนัก (กล่าวคือ น้ำหนักของเส้นเชื่อมทุกเส้นเป็น 1) ที่ทำให้ $\sum_{i=1}^{n} \sum_{j=i+1}^{n} \operatorname{dis}(i, j) = x$ โดยที่ $\operatorname{dis}(i, j)$ แทนความยาวของวิถีสั้นที่สุดระหว่างจุดยอด $i$ และจุดยอด $j$
ปัญหานี้แน่นอนว่าง่ายมาก... แต่น่าเสียดายที่ทรัพยากรของคุณมีจำกัด ดังนั้นคุณจึงต้องการหากราฟที่มีจำนวนจุดยอดไม่เกิน 85 จุดที่ตรงตามข้อกำหนด
ข้อมูลนำเข้า
หนึ่งชุดทดสอบประกอบด้วยหลายชุดข้อมูล
บรรทัดแรกของข้อมูลนำเข้าคือจำนวนชุดข้อมูล $T$ ($1 \le T \le 2000$) ซึ่งแทนจำนวนชุดข้อมูลที่มีอยู่ในชุดทดสอบนี้
สำหรับแต่ละชุดข้อมูล จะมีหนึ่งบรรทัดที่มีจำนวนเต็ม $x$ ($1 \le x \le 10^5$) ซึ่งแทนเงื่อนไขที่ต้องทำให้เป็นจริง รับประกันว่ามีกราฟที่มีจุดยอดไม่เกิน 85 จุดอย่างน้อยหนึ่งกราฟที่ตรงตามเงื่อนไข
ข้อมูลส่งออก
สำหรับแต่ละชุดข้อมูล ให้แสดงผลจำนวนจุดยอด $n$ ที่คุณใช้ในบรรทัดแรก ($2 \le n \le 85$) จากนั้นแสดงผลอีก $n - 1$ บรรทัด โดยบรรทัดที่ $i$ เป็นสตริงฐานสองที่มีความยาว $n - i$ อักขระตัวที่ $j$ ของบรรทัดที่ $i$ จะเป็น 1 ก็ต่อเมื่อมีเส้นเชื่อมระหว่างจุดยอด $i$ และจุดยอด $i + j$
ตัวอย่าง
ข้อมูลนำเข้า
4 1 3 6 8
ข้อมูลส่งออก
2 1 3 11 1 4 111 11 1 4 110 10 1