extern crate core;

use std::fmt;
use std::cmp::{Ordering, min, max};
use std::fmt::{Display, Error, Formatter};
use std::f32::MAX;
use std::ops::{Add, Sub, Mul, Div, Neg, Index, IndexMut};
use std::collections::{BTreeMap, VecDeque, BinaryHeap};

fn show<T: Display>(vec: &Vec<T>) {
    if vec.is_empty() {
        println!("[]");
    }else {
        print!("[{}", vec[0]);
        for i in 1 .. vec.len() {
            print!(", {}", vec[i]);
        }
        println!("]");
    }
}
fn show2<T: Display>(vec: &Vec<Vec<T>>) {
    if vec.is_empty() {
        println!("[]");
    }else {
        for l in vec {
            show(l);
        }
    }
}
macro_rules! read_line{
    () => {{
        let mut line = String::new();
        std::io::stdin().read_line(&mut line).ok();
        line
    }};
    (delimiter: ' ') => {
        read_line!().split_whitespace().map(|x|x.to_string()).collect::<Vec<_>>()
    };
    (delimiter: $p:expr) => {
        read_line!().split($p).map(|x|x.to_string()).collect::<Vec<_>>()
    };
    (' ') => {
        read_line!(delimiter: ' ')
    };
    ($delimiter:expr) => {
        read_line!(delimiter: $delimiter)
    };
    (' '; $ty:ty) => {
        read_line!().split_whitespace().map(|x|x.parse::<$ty>().ok().unwrap()).collect::<Vec<$ty>>()
    };
    ($delimiter:expr; $ty:ty) => {
        read_line!($delimiter).into_iter().map(|x|x.parse::<$ty>().ok().unwrap()).collect::<Vec<$ty>>()
    };
}
macro_rules! read_value{
    () => {
        read_line!().trim().parse().ok().unwrap()
    }
}
macro_rules! let_all {
    ($($n:ident:$t:ty),*) => {
        let line = read_line!(delimiter: ' ');
        let mut iter = line.iter();
        $(let $n:$t = iter.next().unwrap().parse().ok().unwrap();)*
    };
}
macro_rules! let_mut_all {
    ($($n:ident:$t:ty),*) => {
        let line = read_line!(delimiter: ' ');
        let mut iter = line.iter();
        $(let mut $n:$t = iter.next().unwrap().parse().ok().unwrap();)*
    };
}
#[derive(Copy, Clone)]
struct Road {
    to: usize, id: usize
}
#[derive(Copy, Clone)]
struct ValueWithKey<K: Copy + Clone, V: Copy + Clone>{
    key: K, value: V,
}
impl <K: Copy + Clone, V: Copy + Clone> ValueWithKey<K, V> {
    fn new(key: K, value: V) -> ValueWithKey<K, V> {
        ValueWithKey{value: value, key: key}
    }
}
impl <K: Ord + Copy + Clone, V: Copy + Clone> Ord for ValueWithKey<K, V> {
    fn cmp(&self, other: &Self) -> Ordering {
        other.key.cmp(&self.key)
    }
}
impl <K: PartialOrd + Copy + Clone, V: Copy + Clone> PartialOrd for ValueWithKey<K, V> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        other.key.partial_cmp(&self.key)
    }
}
impl <K: PartialEq + Copy + Clone, V: Copy + Clone> PartialEq for ValueWithKey<K, V> {
    fn eq(&self, other: &Self) -> bool {
        other.key.eq(&self.key)
    }
}
impl <K: Eq + Copy + Clone, V: Copy + Clone> Eq for ValueWithKey<K, V>{}
fn main() {
    loop {
        let_all!(n: usize);
        if n == 0 {
            return
        }
        let_all!(s: usize, t: usize);
        let_all!(m: usize);
        let mut roads = vec![Vec::new(); n];
        let mut rev_roads = vec![Vec::new(); n];
        for i in 0 .. m {
            let_all!(a: usize, b: usize);
            roads[a - 1].push(Road{to: b - 1, id: i});
            rev_roads[b - 1].push(Road{to: a - 1, id: i});
        }
        let mut min_rev_roads = vec![m; n];
        let mut min_distance = vec![std::usize::MAX; n];
        let mut rev_min_distance = vec![std::usize::MAX; n];
        let mut queue = VecDeque::new();
        min_distance[s - 1] = 0;
        queue.push_back(ValueWithKey::new(0, s - 1));
        while let Some(ValueWithKey{key: distance, value: current}) = queue.pop_front() {
            if min_distance[current] == distance {
                for &Road{to: next, id:_} in &roads[current] {
                    if min_distance[next] > distance + 1 {
                        min_distance[next] = distance + 1;
                        queue.push_back(ValueWithKey::new(distance + 1, next));
                    }
                }
                for &Road{to: next, id: id} in &rev_roads[current] {
                    if rev_min_distance[next] > distance + 1 {
                        rev_min_distance[next] = distance + 1;
                        min_rev_roads[next] = id;
                    }else if rev_min_distance[next] == distance + 1 && min_rev_roads[next] > id {
                        min_rev_roads[next] = id;
                    }
                }
            }
        }
        let mut queue = BinaryHeap::new();
        for i in 0 .. n {
            if rev_min_distance[i] != std::usize::MAX {
                queue.push(ValueWithKey::new(rev_min_distance[i], i));
            }
        }
        while let Some(ValueWithKey{key: distance, value: current}) = queue.pop() {
            if rev_min_distance[current] == distance {
                for &Road{to: next, id: _} in &roads[current] {
                    if rev_min_distance[next] > distance + 1 {
                        rev_min_distance[next] = distance + 1;
                        min_rev_roads[next] = min_rev_roads[current];
                        queue.push(ValueWithKey::new(distance + 1, next));
                    }else if rev_min_distance[next] == distance + 1 && min_rev_roads[next] > min_rev_roads[current] {
                        min_rev_roads[next] = min_rev_roads[current];
                    }
                }
            }
        }
        if min_distance[t - 1] > rev_min_distance[t - 1] {
            println!("{} {}", rev_min_distance[t - 1], min_rev_roads[t - 1] + 1);
        }else {
            println!("{} 0", min_distance[t - 1]);
        }
    }
}


Measured memory_bytes: 5048