تقدم شركة هواتف محمولة العرض الترويجي التالي: يمكن لكل عميل جديد اختيار $k$ بالضبط من أرقام الهواتف الأخرى، وتكون جميع المكالمات بين العميل وأي من جهات الاتصال الـ $k$ المختارة مجانية (في كلا الاتجاهين).
يرغب مجموعة من $n$ طلاب (مرقمين من $1$ إلى $n$) في الاستفادة من هذا العرض. يجب على كل طالب $i$ اختيار $k$ بالضبط من جهات الاتصال المختلفة من المجموعة $\{1, 2, \dots, n\} \setminus \{i\}$.
نقول إن طالبين $i$ و $j$ يمكنهما التحدث مجاناً إذا تحقق شرط واحد على الأقل مما يلي:
- اختار $i$ الطالب $j$ كواحد من جهات الاتصال المجانية، أو
- اختار $j$ الطالب $i$ كواحد من جهات الاتصال المجانية.
يريد الطلاب اختيار جهات الاتصال المجانية الخاصة بهم بحيث يتمكن أي طالب من التحدث إلى أي طالب آخر مجاناً، أي أنه لكل زوج $(i, j)$ يحقق $1 \le i < j \le n$، يمكن للطالبين $i$ و $j$ التحدث مجاناً.
من أجل قيمة معطاة $k$، مهمتك هي:
- تحديد أكبر عدد ممكن $n$ من الطلاب يكون فيه مثل هذا التوزيع ممكناً،
- بناء توزيع صالح واحد لجهات الاتصال المختارة من أجل هذا العدد الأقصى $n$.
الإدخال
يتكون الإدخال من عدد صحيح واحد $k$.
الإخراج
في السطر الأول، اطبع عدداً صحيحاً واحداً $n$ — الحد الأقصى لعدد الطلاب الذين يمكنهم اختيار جهات الاتصال المجانية بحيث يتمكن أي طالبين من التحدث مع بعضهما البعض مجاناً.
في الأسطر الـ $n$ التالية، اطبع جهات الاتصال المجانية الـ $k$ التي اختارها كل طالب: في السطر $i+1$ (لكل $1 \le i \le n$)، اطبع $k$ من الأعداد الصحيحة المختلفة $a_{i,1}, a_{i,2}, \dots, a_{i,k}$. يجب أن يحقق كل $a_{i,j}$ الشرطين $1 \le a_{i,j} \le n$ و $a_{i,j} \neq i$. تشير هذه الأسطر إلى أن الطالب $i$ قد اختار الطلاب $a_{i,1}, a_{i,2}, \dots, a_{i,k}$ كجهات اتصال مجانية له.
إذا كانت هناك عدة إجابات صالحة، فاطبع أياً منها.
القيود
- $1 \le k \le 1000$.
مثال 1
2
5
2 5
3 4
1 5
1 3
2 4
ملاحظات
في المثال، $k = 2$ والحد الأقصى لعدد الطلاب الذين يمكنهم اختيار جهات الاتصال المجانية بحيث يتمكن أي طالبين من التحدث مع بعضهما البعض مجاناً هو $n = 5$. لكل زوج من الطلاب المختلفين، اختار أحدهما على الأقل الآخر، لذا يمكن لأي اثنين التحدث مجاناً.