#Copyright (c) 2008 Cao Li http://shiningray.cn/
#
#Permission is hereby granted, free of charge, to any person obtaining a copy
#of this software and associated documentation files (the "Software"), to deal
#in the Software without restriction, including without limitation the rights
#to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
#copies of the Software, and to permit persons to whom the Software is
#furnished to do so, subject to the following conditions:
#
#The above copyright notice and this permission notice shall be included in
#all copies or substantial portions of the Software.
#
#THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
#IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
#FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
#AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
#LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
#OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
#THE SOFTWARE.
#
#
# A simple tool for generating a graph test case for SPOJ SHPATH problem
#
from random import randint
from collections import defaultdict
size = 10000
m = defaultdict(dict)
for i in xrange(1, size+1):
s = i + randint(1, size/10)
e = min(s + randint(1,size/10), size+1)
for j in xrange(s, e, randint(1, 10)):
m[i][j] = randint(1,1000)
m[j][i] = m[i][j]
print 1
print len(m)
for i, edges in m.iteritems():
print "p" + str(i)
print len(edges)
for j, v in edges.iteritems():
print j, v
print 10
lm = len(m)
h = lm // 2
lm -= 1
for i in xrange(10):
print "p%d p%d" % (randint(1,h), randint(h+1, lm))