Самый быстрый способ читать stdin в Python?
raw_input применяется для интерактивного ввода.

Скорее всего вам нужно пользоваться sys.stdin.read(), или sys.stdin.readlines(), или итеративно через генератор (for line in sys.stdin).
По идее, использование спискового выражения должно дать небольшой бонус:

def main():
  for case in xrange(int(raw_input())):
    pairs = [map(int, raw_input().split()) for _ in raw_input().split()]
    print 'Scenario #%d:' % (case + 1)
    solve(pairs)
