#include #include #include #include #include #include using namespace std; const int MAX_STATION = 1024; const int MAX_TRAIN = 128; int n, m; int table[MAX_STATION]; typedef vector > Stops; struct Train { Stops s; int i; bool run; int sleep; int sleep_max; bool prepare(int start) { for(i = 0; i < (int)s.size(); ++i) if(s[i].second >= start) break; run = true; sleep = -1; sleep_max = 0; return i < (int)s.size(); } bool next(int end) { if(run && sleep >= 0) { sleep_max = max(sleep_max, sleep); table[s[i].first] = max(table[s[i].first], sleep_max); } else if(!run) { if(table[s[i].first] >= 0) sleep = max(sleep, 0); if(sleep >= 0) sleep += s[i+1].second - s[i].second; sleep_max = max(sleep_max, table[s[i].first]); ++i; } run = !run; return (run || i+1 < (int)s.size()) && s[i].second <= end; } int getTime() const { return s[i].second * 2 + !run; } }; Train train[MAX_TRAIN]; int Solve(int src_p, int src_t, int dst_p, int dst_t) { fill_n(table, n, -1); multimap up; if(src_t > dst_t) return -1; table[src_p] = 0; for(int i = 0; i < m; ++i) if(train[i].prepare(src_t)) up.insert(make_pair(train[i].getTime(), i)); while(!up.empty()) { int ti = up.begin()->second; up.erase(up.begin()); if(train[ti].next(dst_t)) up.insert(make_pair(train[ti].getTime(), ti)); } return table[dst_p]; } int ReadTime(istream& s) { int h, m; char c; s >> h >> c >> m; return h*60 + m; } int ReadPos(istream& s) { int p; s >> p; --p; return p; } int main() { ifstream cin("D.txt"); while(cin >> n >> m && n) { int sp = ReadPos(cin); int st = ReadTime(cin); int dp = ReadPos(cin); int dt = ReadTime(cin); for(int i = 0; i < m; ++i) { int k; cin >> k; train[i].s.resize(k); for(int j = 0; j < k; ++j) { train[i].s[j].first = ReadPos(cin); train[i].s[j].second = ReadTime(cin); } } int ans = Solve(sp, st, dp, dt); if(ans >= 0) cout << ans << endl; else cout << "impossible" << endl; } }